Submission #1264735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264735		nai0610	Election (BOI18_election)	C++20	100 / 100	517 ms	21720 KiB

election

#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =5e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int n,q,a[maxn];
struct nai{
	int pre,suf,s,res;
	nai operator+(const nai& other) const {
		return {max(pre,s+other.pre),max(other.suf,other.s+suf),s+other.s,
				max({res+other.s,s+other.res,pre+other.suf})};
	}
} t[maxn*4];
void build(int id,int l,int r){
	if (l==r) {
		t[id]={max(0,a[l]),max(0,a[l]),a[l],(a[l]==1?1:0)};
		return;
	}
	int mid =(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	t[id]=t[id*2]+t[id*2+1];
}
nai get(int id,int l,int r,int u,int v) {
	if (r<u||l>v) return {0,0,0,0};
	if (l>=u&&r<=v) return t[id];
	int mid =(l+r)/2;
	return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}
int main() {
    // freopen("../input.inp","r",stdin);
    // freopen("output.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t start,end;
	start=clock();
	cin>>n;
	for (int i=1;i<=n;i++) {
		char c;
		cin >>c;
		a[i]=(c=='T'?1:-1);
	}
	build(1,1,n);
	cin>>q;
	while (q--) {
		int l,r;
		cin>>l>>r;
		cout <<get(1,1,n,l,r).res<<'\n';
	}
	end=clock();
	ld dur=(ld)(end-start)/(ld)(CLOCKS_PER_SEC)*(1000.0L);
	cerr<<dur<<'\n';
    return 0;
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18