oj.uz

Submission #290712

# Submission time Handle Problem Language Result Execution time Memory
290712 2020-09-04T10:56:16 Z Gurban Election (BOI18_election) C++17
100 / 100
 1799 ms 61200 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 5e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n,q,M[4*maxn][3],T[4*maxn][3],ans[maxn];
string s;
stack<int>last;

void prop(int tp,int nd){
	if(tp==0){
		T[nd*2][0] += T[nd][1];
		T[nd*2][1] += T[nd][1];
		T[nd*2+1][0] += T[nd][1];
		T[nd*2+1][1] += T[nd][1];
		T[nd][1] = 0;
	}
	else {
		M[nd*2][0] += M[nd][1];
		M[nd*2][1] += M[nd][1];
		M[nd*2+1][0] += M[nd][1];
		M[nd*2+1][1] += M[nd][1];
		M[nd][1] = 0;
	}
}	

void upd(int val,int a,int b,int l,int r,int nd){
	if(r < a or l > b) return;
	if(l >= a and r <= b){T[nd][0] += val,T[nd][1] += val;return;}
	
	prop(0,nd);
	upd(val,a,b,l,(l+r)/2,nd*2);
	upd(val,a,b,(l+r)/2+1,r,nd*2+1);

	T[nd][0]=min(T[nd*2][0],T[nd*2+1][0]);
}

int tap(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return mod;
	if(l >= a and r <= b) return T[nd][0];
	prop(0,nd);
	return min(tap(a,b,l,(l+r)/2,nd*2),tap(a,b,(l+r)/2+1,r,nd*2+1));
}

void upd1(int val,int a,int b,int l,int r,int nd){
	if(r < a or l > b) return;
	if(l >= a and r <= b){M[nd][0] += val,M[nd][1] += val;return;}
	
	prop(1,nd);
	upd1(val,a,b,l,(l+r)/2,nd*2);
	upd1(val,a,b,(l+r)/2+1,r,nd*2+1);

	M[nd][0]=max(M[nd*2][0],M[nd*2+1][0]);
}

int tap1(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return 0;
	if(l >= a and r <= b) return M[nd][0];
	prop(1,nd);
	return max(tap1(a,b,l,(l+r)/2,nd*2),tap1(a,b,(l+r)/2+1,r,nd*2+1));
}

int main(){
	#ifdef LOCAL
		clock_t TSTART = clock();
	#endif
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> s >> q;
	vector<pii>v[n];
	int a,b;
	for(int i = 0;i < q;i++){
		cin >> a >> b;
		v[a-1].pb({b-1,i});
	}

	// for(int i = n-1;i >= 0;i--){
	// 	if(sz(v[i])){
	// 		cout<<i<<" ---> ";
	// 		for(auto j : v[i]) cout<<j.ff<<' ';
	// 		cout<<'\n';
	// 	}
	// }
	for(int i = n-1;i >= 0;i--){
		if(s[i]=='C'){
			upd(1,i,n-1,0,n-1,1);
			upd1(1,i,n-1,0,n-1,1);
			if(!last.empty()){
				int pos=last.top(); 
				last.pop();
				upd1(-1,pos,n-1,0,n-1,1);
			}
		}
		else {
			upd(-1,i,n-1,0,n-1,1);
			last.push(i);
		}
		// for(int j = 0;j < n;j++) cout<<tap1(j,j,0,n-1,1)<<' ';
		// cout<<'\n';
		for(auto j : v[i]){
			a = tap(i,j.ff,0,n-1,1);
			b = tap1(i,j.ff,0,n-1,1);
			int val = tap1(j.ff,j.ff,0,n-1,1);
			// cout<<a<<' '<<b<<' '<<val<<'\n';
			ans[j.ss]=b-val-min(0,a);
		}
	}
	for(int i = 0;i < q;i++) cout<<ans[i]<<'\n';

	#ifdef LOCAL
		cout << "\nTime elapsed: " << double(clock()-TSTART) / CLOCKS_PER_SEC << " s.\n";
	#endif
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 181 ms 11256 KB Output is correct
7 Correct 164 ms 10744 KB Output is correct
8 Correct 169 ms 10744 KB Output is correct
9 Correct 157 ms 11128 KB Output is correct
10 Correct 194 ms 11128 KB Output is correct
11 Correct 173 ms 11384 KB Output is correct
12 Correct 181 ms 11256 KB Output is correct
13 Correct 177 ms 11420 KB Output is correct
14 Correct 182 ms 11256 KB Output is correct
15 Correct 186 ms 11256 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 4 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 181 ms 11256 KB Output is correct
7 Correct 164 ms 10744 KB Output is correct
8 Correct 169 ms 10744 KB Output is correct
9 Correct 157 ms 11128 KB Output is correct
10 Correct 194 ms 11128 KB Output is correct
11 Correct 173 ms 11384 KB Output is correct
12 Correct 181 ms 11256 KB Output is correct
13 Correct 177 ms 11420 KB Output is correct
14 Correct 182 ms 11256 KB Output is correct
15 Correct 186 ms 11256 KB Output is correct
16 Correct 1769 ms 59532 KB Output is correct
17 Correct 1490 ms 55564 KB Output is correct
18 Correct 1672 ms 56616 KB Output is correct
19 Correct 1451 ms 58340 KB Output is correct
20 Correct 1758 ms 58784 KB Output is correct
21 Correct 1736 ms 60940 KB Output is correct
22 Correct 1786 ms 60400 KB Output is correct
23 Correct 1744 ms 61200 KB Output is correct
24 Correct 1784 ms 60696 KB Output is correct
25 Correct 1799 ms 59660 KB Output is correct