Submission #377605

#	Time	Username	Problem	Language	Result	Execution time	Memory
377605		negar_a	Zagrade (COI17_zagrade)	C++14	0 / 100	184 ms	18560 KiB

zagrade

//!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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60