?
| # | 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 |
#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;
}
?
?
?
?