oj.uz

Submission #928937

# Submission time Handle Problem Language Result Execution time Memory
928937 2024-02-17T08:36:36 Z FanOfWilliamLin Election (BOI18_election) C++17
100 / 100
 596 ms 44388 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define ll long long
#define ld long double
#define ar array
#define vt vector
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define lla(v) v.rbegin(), v.rend()

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb)/2;
		f(mb)?rb=mb:lb=mb+1; 
	} 
	return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
	while(lb<rb) {
		ll mb=(lb+rb+1)/2;
		f(mb)?lb=mb:rb=mb-1; 
	} 
	return lb;
}

const ll INF=1000000000000000000LL;
const ll MOD=1e9+7;
const ll M=(1ll<<61)-1;
//const ll MOD=998244353; //sometimes need to be used

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const ll base=uniform_int_distribution<ll>(0, M-1)(rng);

ll bpow(ll a, ll b, ll DOM) {
	a%=DOM;
	ll res=1;
	while(b>0) {
		if(b&1)
			res=res*a%DOM;
		a=a*a%DOM;
		b>>=1;
	}
	return res;
}

int gcd_x, gcd_y, gcd_d;

int gcd(int a, int b) {
	if (!b) {
        gcd_x=1;
        gcd_y=0;
        return a;
    }
    gcd_d=gcd(b, a%b);
	int tmp=gcd_x;
	gcd_x=gcd_y;
	gcd_y=tmp-(a/b)*gcd_y;
    return gcd_d;
}

ll floor_div(ll x, ll y) {
	assert(y!=0);
	if (y<0) {
		y=-y;
		x=-x;
	}
	if (x>=0) return x/y;
	return (x+1)/y-1;
}
ll ceil_div(ll x, ll y) {
	assert(y!=0);
	if (y<0) {
		y=-y;
		x=-x;
	}
	if (x<=0) {
		return x/y;
	}
	return (x-1)/y+1;
}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

const int mxN=5e5+1;
int n, q;
string s;

struct Nodes {
	int mx_pref, mx_suf;
	int sum;
	int ans;
} ST[1<<20];

// 1: Cap
// 0: Tony

Nodes combine(const Nodes& a, const Nodes& b) {
	Nodes res;
	res.mx_pref=max(a.mx_pref, a.sum+b.mx_pref);
	res.mx_suf=max(b.mx_suf, a.mx_suf+b.sum);
	res.sum=a.sum+b.sum;
	res.ans=max(max(a.ans+b.sum, a.sum+b.ans), a.mx_pref+b.mx_suf);
	return res;
}

void upd(int pos, bool val, int id=1, int l=1, int r=n) {
	if(pos<l||pos>r) {
		return;
	}
	if(l==r) {
		// +1: Tony
		// -1: Cap
		if(!val) {
			ST[id].mx_pref=1;
			ST[id].mx_suf=1;
			ST[id].sum=1;
			ST[id].ans=1;
		}
		else {
			ST[id].mx_pref=0;
			ST[id].mx_suf=0;
			ST[id].sum=-1;
			ST[id].ans=0;
		}
		return;
	}
	int mid=(l+r)/2;
	upd(pos, val, 2*id, l, mid);
	upd(pos, val, 2*id+1, mid+1, r);
	ST[id]=combine(ST[2*id], ST[2*id+1]);
}

Nodes qury(int u, int v, int id=1, int l=1, int r=n) {
	if(u>r||l>v) {
		return {0, 0, 0, 0};
	}
	if(l>=u&&v>=r) {
		return ST[id];
	}
	int mid=(l+r)/2;
	return combine(qury(u, v, 2*id, l, mid), qury(u, v, 2*id+1, mid+1, r));
}

void solve() {
	//solve here
	cin >> n;
	cin >> s;
	s=" "+s;
	for(int i=1; i<=n; ++i) {
		if(s[i]=='C') {
			upd(i, 1);
		}
		else {
			upd(i, 0);
		}
	}
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		cout << qury(l, r).ans << "\n";
	}
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	//freopen("template.inp", "r", stdin);
	//freopen("template.out", "w", stdout);	

	int TC=1;
	//cin >> TC;
	while(TC--) {
		solve();
	}
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 58 ms 10208 KB Output is correct
7 Correct 57 ms 10156 KB Output is correct
8 Correct 56 ms 10060 KB Output is correct
9 Correct 63 ms 9916 KB Output is correct
10 Correct 58 ms 10064 KB Output is correct
11 Correct 59 ms 10060 KB Output is correct
12 Correct 58 ms 10140 KB Output is correct
13 Correct 59 ms 10320 KB Output is correct
14 Correct 58 ms 10232 KB Output is correct
15 Correct 59 ms 10064 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 58 ms 10208 KB Output is correct
7 Correct 57 ms 10156 KB Output is correct
8 Correct 56 ms 10060 KB Output is correct
9 Correct 63 ms 9916 KB Output is correct
10 Correct 58 ms 10064 KB Output is correct
11 Correct 59 ms 10060 KB Output is correct
12 Correct 58 ms 10140 KB Output is correct
13 Correct 59 ms 10320 KB Output is correct
14 Correct 58 ms 10232 KB Output is correct
15 Correct 59 ms 10064 KB Output is correct
16 Correct 546 ms 43556 KB Output is correct
17 Correct 462 ms 43000 KB Output is correct
18 Correct 567 ms 43360 KB Output is correct
19 Correct 469 ms 43116 KB Output is correct
20 Correct 560 ms 42400 KB Output is correct
21 Correct 553 ms 44280 KB Output is correct
22 Correct 560 ms 44224 KB Output is correct
23 Correct 596 ms 44388 KB Output is correct
24 Correct 557 ms 44132 KB Output is correct
25 Correct 565 ms 43588 KB Output is correct