oj.uz

Submission #875855

# Submission time Handle Problem Language Result Execution time Memory
875855 2023-11-20T16:11:35 Z 1075508020060209tc Election (BOI18_election) C++14
100 / 100
 1292 ms 68936 KB 
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int Q;
string s;
int ar[500005];
int ps[500005];
struct SGTR{
int l;int r;
int mn;
int psmn;int sfmn;
int sum;
}tr[2000006];

void pull(int nw){
tr[nw].sum=tr[nw*2].sum+tr[nw*2+1].sum;
tr[nw].psmn=min(tr[nw*2].psmn,tr[nw*2].sum+tr[nw*2+1].psmn);
tr[nw].sfmn=min(tr[nw*2+1].sfmn,tr[nw*2+1].sum+tr[nw*2].sfmn);
tr[nw].mn=min({tr[nw*2].mn,tr[nw*2+1].mn,tr[nw*2].sfmn+tr[nw*2+1].psmn});
}

void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
if(l==r){
    tr[nw].sum=ar[l];
    tr[nw].psmn=min(ar[l],0ll);
    tr[nw].sfmn=min(ar[l],0ll);
    tr[nw].mn=min(ar[l],0ll);
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);buildtr(nw*2+1,mi+1,r);
pull(nw);
}
int psmn;
int ans;
void qry(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
  //  cout<<nw<<" "<<tr[nw].l<<" "<<tr[nw].r<<" "<<tr[nw].psmn<<" "<<tr[nw].sfmn<<" "<<tr[nw].sum<<"\n";
    ans=min(ans,tr[nw].mn);
    ans=min(ans,tr[nw].psmn+psmn);
    psmn=min(psmn+tr[nw].sum,tr[nw].sfmn);
    return;
}
if(tr[nw].l>r||tr[nw].r<l){return;}
qry(nw*2,l,r);qry(nw*2+1,l,r);
}




signed main()
{
    cin>>n>>s;
    for(int i=1;i<=n;i++){
        if(s[i-1]=='T'){
            ar[i]=1;
        }else{
            ar[i]=-1;
        }
        ps[i]=ar[i]+ps[i-1];
    }
    buildtr(1,1,n);



    cin>>Q;
    while(Q--){
        int l;int r;
        cin>>l>>r;
        ans=0;
        psmn=0;
        qry(1,l,r);
     //   cout<<ps[r]-ps[l-1]<<" "<<ans<<" ";
        cout<<ps[r]-ps[l-1]-ans<<"\n";
    }

}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 4 ms 4788 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 145 ms 17028 KB Output is correct
7 Correct 133 ms 16812 KB Output is correct
8 Correct 134 ms 16636 KB Output is correct
9 Correct 133 ms 16728 KB Output is correct
10 Correct 138 ms 16796 KB Output is correct
11 Correct 142 ms 16832 KB Output is correct
12 Correct 142 ms 16984 KB Output is correct
13 Correct 143 ms 16976 KB Output is correct
14 Correct 144 ms 16720 KB Output is correct
15 Correct 143 ms 16796 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4700 KB Output is correct
2 Correct 4 ms 4788 KB Output is correct
3 Correct 4 ms 4700 KB Output is correct
4 Correct 4 ms 4700 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 145 ms 17028 KB Output is correct
7 Correct 133 ms 16812 KB Output is correct
8 Correct 134 ms 16636 KB Output is correct
9 Correct 133 ms 16728 KB Output is correct
10 Correct 138 ms 16796 KB Output is correct
11 Correct 142 ms 16832 KB Output is correct
12 Correct 142 ms 16984 KB Output is correct
13 Correct 143 ms 16976 KB Output is correct
14 Correct 144 ms 16720 KB Output is correct
15 Correct 143 ms 16796 KB Output is correct
16 Correct 1287 ms 67860 KB Output is correct
17 Correct 1087 ms 67508 KB Output is correct
18 Correct 1143 ms 68036 KB Output is correct
19 Correct 1064 ms 67244 KB Output is correct
20 Correct 1268 ms 66824 KB Output is correct
21 Correct 1292 ms 68840 KB Output is correct
22 Correct 1273 ms 68628 KB Output is correct
23 Correct 1268 ms 68936 KB Output is correct
24 Correct 1254 ms 68424 KB Output is correct
25 Correct 1257 ms 68140 KB Output is correct