If you feel interested in joining Nebius as a full-time employee, go on and fill the form. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
197201278 Practice:
shivanshsingh9670
380C - 18 GNU C++17 Time limit exceeded on test 13 1000 ms 173532 KB 2023-03-13 10:57:41 2023-03-13 10:57:41
 
 
→ Source
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void build(ll i, ll beg, ll end, string &s, vector<vector<ll>> &segment){
    if(beg == end){
        ll open = s[beg]=='(' ? 1 : 0;
        ll close = s[beg]==')' ? 1 : 0;
        ll full = 0;
        segment[i] = {open, close, full};
        return ;
    }
    
    ll mid = beg + (end-beg)/2;
    
    build(2*i + 1, beg, mid, s, segment);
    build(2*i + 2, mid+1, end, s, segment);
    
    ll open1 = segment[2*i + 1][0], close1 = segment[2*i + 1][1], full1 = segment[2*i + 1][2];
    ll open2 = segment[2*i + 2][0], close2 = segment[2*i + 2][1], full2 = segment[2*i + 2][2];
    
    ll full = full1 + full2;
    ll temp = min(open1, close2);
    full += 2*temp;
    open1 -= temp;
    close2 -= temp;
    ll open = open1 + open2;
    ll close = close1 + close2;
    
    segment[i] = {open, close, full};
}

vector<ll> query(ll i, ll beg, ll end, ll &l, ll &r, vector<vector<ll>> &segment){
    if(r<beg || l>end)    // No Overlap
    return {0, 0, 0};
    
    if(l<=beg && r>=end)    // Complete Overlap
    return segment[i];
    
    ll mid = beg + (end-beg)/2;
    
    vector<ll> left = query(2*i + 1, beg, mid, l, r, segment);
    vector<ll> right = query(2*i + 2, mid+1, end, l, r, segment);
    
    ll open1 = left[0], close1 = left[1], full1 = left[2];
    ll open2 = right[0], close2 = right[1], full2 = right[2];
    
    ll full = full1 + full2;
    ll temp = min(open1, close2);
    full += 2*temp;
    open1 -= temp;
    close2 -= temp;
    ll open = open1 + open2;
    ll close = close1 + close2;
    
    return {open, close, full};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s;
    cin>>s;
    
    ll q;
    cin>>q;
    
    ll n = s.length();
    
    vector<vector<ll>> segment(4*n, {0, 0, 0});
    
    build(0, 0, n-1, s, segment);
    
    while(q--){
        ll l, r;
        cin>>l>>r;
        l -= 1;
        r -= 1;
        cout<<query(0, 0, n-1, l, r, segment)[2]<<"\n";
    }
    
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details