| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 377605 |
2021-03-14T11:27:40 Z |
negar_a |
Zagrade (COI17_zagrade) |
C++14 |
|
184 ms |
18560 KB |
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
struct node{
int mn, td, lzy;
};
const int maxn = 3e5 + 10;
int dif[maxn];
node seg[maxn * 4];
void build(int l, int r, int x){
seg[x].lzy = 0;
if(l + 1 >= r){
seg[x].mn = dif[l + 1];
seg[x].td = 1;
return;
}
int mid = (l + r) / 2;
build(l, mid, x * 2);
build(mid, r, x * 2 + 1);
seg[x].mn = min(seg[x * 2].mn, seg[x * 2 + 1].mn);
seg[x].td = 0;
if(seg[x * 2].mn == seg[x].mn){
seg[x].td += seg[x * 2].td;
}
if(seg[x * 2 + 1].mn == seg[x].mn){
seg[x].td += seg[x * 2 + 1].td;
}
}
void add(int v){
seg[1].lzy += v;
seg[1].mn += v;
}
void shift(int l, int r, int x){
if(l + 1 >= r || seg[x].lzy == 0){
return;
}
seg[x * 2].lzy += seg[x].lzy;
seg[x * 2 + 1].lzy += seg[x].lzy;
seg[x * 2].mn += seg[x].lzy;
seg[x * 2 + 1].mn += seg[x].lzy;
seg[x].lzy = 0;
}
int get(int l, int r, int ind, int x){
shift(l, r, x);
if(l + 1 >= r){
return seg[x].mn;
}
int mid = (l + r) / 2;
if(ind < mid){
return get(l, mid, ind, x * 2);
}else{
return get(mid, r, ind, x * 2 + 1);
}
}
int fin(int l, int r, int L, int x){
shift(l, r, x);
if(seg[x].mn >= 0){
return -1;
}
if(l + 1 >= r){
return l;
}
int mid = (l + r) / 2;
if(L < mid){
int t = fin(l, mid, L, x * 2);
if(t != -1){
return t;
}else{
return fin(mid, r, L, x * 2 + 1);
}
}else{
return fin(mid, r, L, x * 2 + 1);
}
}
int ted(int l, int r, int L, int R, int x){
if(l >= R || r <= L){
return 0;
}
if(l >= L && r <= R){
return (seg[x].mn == 0) ? seg[x].td : 0;
}
int mid = (l + r) / 2;
return ted(l, mid, L, R, x * 2) + ted(mid, r, L, R, x * 2 + 1);
}
int main(){
fast_io;
int n;
cin >> n;
string s;
cin >> s;
for(int i = 0; i < n - 1; i ++){
int x, y;
cin >> x >> y;
}
for(int i = 0; i < n; i ++){
dif[i + 1] = dif[i] - (s[i] == ')') + (s[i] == '(');
}
build(0, n, 1);
ll ans = 0;
for(int i = 0; i < n; i ++){
int v = get(0, n, i, 1);
if(v == 1){
// cout << "ghar" << endl;
int x = n;
if(seg[1].mn < 0){
// cout << "koochik! ";
x = fin(0, n, i, 1);
// cout << x << endl;
}
ans += ted(0, n, i, x, 1);
}
add((s[i] == ')') - (s[i] == '('));
// cout << "ans = " << ans << endl;
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
184 ms |
18560 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
