oj.uz

Submission #713599

# Submission time Handle Problem Language Result Execution time Memory
713599 2023-03-22T15:43:43 Z JJAnawat Election (BOI18_election) C++17
100 / 100
 500 ms 28064 KB 
#include<bits/stdc++.h>

using namespace std;

struct node{
    int l,r,s,ans;

    node(int ll=0,int rr=0,int ss=0,int aa=0){
        l=ll;
        r=rr;
        s=ss;
        ans=aa;
    }
};

node seg[1<<20];
string ss;

node mer(node ln,node rn){
    node res;
    res.l=max(ln.l,ln.s+rn.l);
    res.r=max(rn.r,rn.s+ln.r);
    res.s=ln.s+rn.s;
    res.ans=max({ln.l+rn.r,ln.ans+rn.s,ln.s+rn.ans});
    return res;
}

void build(int l,int r,int i){
    if(l==r){
        if(ss[l]=='T')
            seg[i]=node(1,1,1,1);
        else
            seg[i]=node(0,0,-1,0);
        return;
    }
    int m=(l+r)/2;
    build(l,m,2*i);
    build(m+1,r,2*i+1);
    seg[i]=mer(seg[2*i],seg[2*i+1]);
}

node qr(int l,int r,int i,int x,int y){
    if(l>y||r<x)
        return node();
    if(l>=x&&r<=y)
        return seg[i];
    int m=(l+r)/2;
    return mer(qr(l,m,2*i,x,y),qr(m+1,r,2*i+1,x,y));
}

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    cin >> ss;
    ss=" "+ss;
    build(1,n,1);
    int q;
    cin >> q;
    int l,r;
    while(q--){
        cin >> l >> r;
        cout << qr(1,n,1,l,r).ans << "\n";
    }
}

Compilation message

election.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16740 KB Output is correct
2 Correct 9 ms 16672 KB Output is correct
3 Correct 9 ms 16748 KB Output is correct
4 Correct 9 ms 16764 KB Output is correct
5 Correct 10 ms 16752 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16740 KB Output is correct
2 Correct 9 ms 16672 KB Output is correct
3 Correct 9 ms 16748 KB Output is correct
4 Correct 9 ms 16764 KB Output is correct
5 Correct 10 ms 16752 KB Output is correct
6 Correct 72 ms 18076 KB Output is correct
7 Correct 54 ms 18008 KB Output is correct
8 Correct 54 ms 17992 KB Output is correct
9 Correct 54 ms 17952 KB Output is correct
10 Correct 57 ms 17992 KB Output is correct
11 Correct 80 ms 18096 KB Output is correct
12 Correct 54 ms 18108 KB Output is correct
13 Correct 51 ms 18156 KB Output is correct
14 Correct 59 ms 18100 KB Output is correct
15 Correct 53 ms 18028 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16740 KB Output is correct
2 Correct 9 ms 16672 KB Output is correct
3 Correct 9 ms 16748 KB Output is correct
4 Correct 9 ms 16764 KB Output is correct
5 Correct 10 ms 16752 KB Output is correct
6 Correct 72 ms 18076 KB Output is correct
7 Correct 54 ms 18008 KB Output is correct
8 Correct 54 ms 17992 KB Output is correct
9 Correct 54 ms 17952 KB Output is correct
10 Correct 57 ms 17992 KB Output is correct
11 Correct 80 ms 18096 KB Output is correct
12 Correct 54 ms 18108 KB Output is correct
13 Correct 51 ms 18156 KB Output is correct
14 Correct 59 ms 18100 KB Output is correct
15 Correct 53 ms 18028 KB Output is correct
16 Correct 458 ms 26996 KB Output is correct
17 Correct 382 ms 26476 KB Output is correct
18 Correct 449 ms 26868 KB Output is correct
19 Correct 378 ms 26300 KB Output is correct
20 Correct 465 ms 26040 KB Output is correct
21 Correct 470 ms 27812 KB Output is correct
22 Correct 484 ms 27748 KB Output is correct
23 Correct 463 ms 28064 KB Output is correct
24 Correct 465 ms 27596 KB Output is correct
25 Correct 500 ms 27092 KB Output is correct