oj.uz

Submission #608903

# Submission time Handle Problem Language Result Execution time Memory
608903 2022-07-27T11:06:55 Z Urvuk3 Election (BOI18_election) C++17
100 / 100
 1103 ms 42920 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll INF=1e9,LINF=1e18,MOD=1e9+7; const ll MAXN=1e3+1,MAXA=1e5+1;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define pb push_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(int i=0;i<sz(x);i++) cerr<<x[i]<<" "; cerr<<endl; }
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct Node{
    int inc,dec,sum,ans;
};

void Solve(){
    int N; cin>>N;
    string S; cin>>S;
    vector<Node> seg(4*(N+1));
    function<Node(Node,Node)> Merge=[&](Node n1,Node n2){
        Node ret;
        ret.inc=max(n1.inc,n1.sum+n2.inc);
        ret.dec=max(n2.dec,n2.sum+n1.dec);
        ret.sum=n1.sum+n2.sum;
        ret.ans=max({n1.sum+n2.ans,n1.ans+n2.sum,n1.inc+n2.dec});
        return ret;
    };
    function<void(int,int,int)> Init=[&](int node,int l,int r){
        if(l==r){
            if(S[l-1]=='T') seg[node]={1,1,1,1};
            else seg[node]={0,0,-1,0};
            return;
        }
        Init(2*node,l,mid); Init(2*node+1,mid+1,r);
        seg[node]=Merge(seg[2*node],seg[2*node+1]);
    };
    function<Node(int,int,int,int,int)> Query=[&](int node,int l,int r,int L,int R){
        if(L<=l && r<=R){
            return seg[node];
        }
        Node ret={0,0,0,0};
        if(L<=mid) ret=Merge(ret,Query(2*node,l,mid,L,R));
        if(R>mid) ret=Merge(ret,Query(2*node+1,mid+1,r,L,R));
        return ret;
    };
    Init(1,1,N);
    int Q; cin>>Q;
    while(Q--){
        int i,j; cin>>i>>j;
        int res=Query(1,1,N,i,j).ans;
        cout<<res<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t; t=1;
    //cin>>t;
    while(t--){
        Solve();
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 105 ms 6044 KB Output is correct
7 Correct 122 ms 6052 KB Output is correct
8 Correct 120 ms 5960 KB Output is correct
9 Correct 86 ms 6084 KB Output is correct
10 Correct 102 ms 5964 KB Output is correct
11 Correct 106 ms 6060 KB Output is correct
12 Correct 106 ms 6112 KB Output is correct
13 Correct 107 ms 6088 KB Output is correct
14 Correct 108 ms 6052 KB Output is correct
15 Correct 110 ms 6064 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 105 ms 6044 KB Output is correct
7 Correct 122 ms 6052 KB Output is correct
8 Correct 120 ms 5960 KB Output is correct
9 Correct 86 ms 6084 KB Output is correct
10 Correct 102 ms 5964 KB Output is correct
11 Correct 106 ms 6060 KB Output is correct
12 Correct 106 ms 6112 KB Output is correct
13 Correct 107 ms 6088 KB Output is correct
14 Correct 108 ms 6052 KB Output is correct
15 Correct 110 ms 6064 KB Output is correct
16 Correct 1049 ms 41944 KB Output is correct
17 Correct 1060 ms 41384 KB Output is correct
18 Correct 1092 ms 41856 KB Output is correct
19 Correct 742 ms 41128 KB Output is correct
20 Correct 1067 ms 40976 KB Output is correct
21 Correct 1103 ms 42792 KB Output is correct
22 Correct 1063 ms 42652 KB Output is correct
23 Correct 1018 ms 42920 KB Output is correct
24 Correct 1066 ms 42444 KB Output is correct
25 Correct 1069 ms 41944 KB Output is correct