oj.uz

Submission #80350

# Submission time Handle Problem Language Result Execution time Memory
80350 2018-10-20T11:11:59 Z igzi Election (BOI18_election) C++17
100 / 100
 1488 ms 105648 KB 
#include <bits/stdc++.h>
#define maxN 500005

using namespace std;

string s;
int n,q,x,y;
struct segment{
int a,l,d,x;
};
segment seg[4*maxN];

void build(int n,int l,int d){
if(l==d){
    if(s[l]=='T'){
        seg[n].a=seg[n].l=seg[n].d=1;
        seg[n].x=-1;
    }
    else{
        seg[n].a=seg[n].l=seg[n].d=0;
        seg[n].x=1;
    }
}
else{
    int m=(l+d)/2;
    build(2*n,l,m);
    build(2*n+1,m+1,d);
    seg[n].l=max(seg[2*n].l,seg[2*n+1].l-seg[2*n].x);
    seg[n].d=max(seg[2*n+1].d,seg[2*n].d-seg[2*n+1].x);
    seg[n].x=seg[2*n].x+seg[2*n+1].x;
    seg[n].a=max(max(seg[2*n].a-seg[2*n+1].x,seg[2*n+1].a-seg[2*n].x),seg[2*n].l+seg[2*n+1].d);
}
}

segment query(int n,int l,int d,int x,int y){
if(l>=x && d<=y) return seg[n];
int m=(l+d)/2;
segment a,b,ans;
a.a=a.l=a.d=a.x=b.a=b.l=b.d=b.x=0;
if(m>=x) a=query(2*n,l,m,x,y);
if(y>=m+1) b=query(2*n+1,m+1,d,x,y);
ans.x=a.x+b.x;
ans.l=max(a.l,b.l-a.x);
ans.d=max(b.d,a.d-b.x);
ans.a=max(max(a.a-b.x,b.a-a.x),a.l+b.d);
return ans;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n;
    cin>>s;
    build(1,0,n-1);
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>x>>y;
        cout<<query(1,0,n-1,x-1,y-1).a<<endl;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 7 ms 540 KB Output is correct
3 Correct 7 ms 560 KB Output is correct
4 Correct 8 ms 600 KB Output is correct
5 Correct 7 ms 880 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 7 ms 540 KB Output is correct
3 Correct 7 ms 560 KB Output is correct
4 Correct 8 ms 600 KB Output is correct
5 Correct 7 ms 880 KB Output is correct
6 Correct 191 ms 6264 KB Output is correct
7 Correct 170 ms 7228 KB Output is correct
8 Correct 176 ms 8108 KB Output is correct
9 Correct 171 ms 8996 KB Output is correct
10 Correct 178 ms 9976 KB Output is correct
11 Correct 201 ms 11004 KB Output is correct
12 Correct 184 ms 12168 KB Output is correct
13 Correct 185 ms 13076 KB Output is correct
14 Correct 181 ms 13924 KB Output is correct
15 Correct 189 ms 14844 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 7 ms 540 KB Output is correct
3 Correct 7 ms 560 KB Output is correct
4 Correct 8 ms 600 KB Output is correct
5 Correct 7 ms 880 KB Output is correct
6 Correct 191 ms 6264 KB Output is correct
7 Correct 170 ms 7228 KB Output is correct
8 Correct 176 ms 8108 KB Output is correct
9 Correct 171 ms 8996 KB Output is correct
10 Correct 178 ms 9976 KB Output is correct
11 Correct 201 ms 11004 KB Output is correct
12 Correct 184 ms 12168 KB Output is correct
13 Correct 185 ms 13076 KB Output is correct
14 Correct 181 ms 13924 KB Output is correct
15 Correct 189 ms 14844 KB Output is correct
16 Correct 1488 ms 37016 KB Output is correct
17 Correct 1369 ms 44244 KB Output is correct
18 Correct 1380 ms 51852 KB Output is correct
19 Correct 1346 ms 58796 KB Output is correct
20 Correct 1475 ms 66084 KB Output is correct
21 Correct 1444 ms 75656 KB Output is correct
22 Correct 1469 ms 83264 KB Output is correct
23 Correct 1461 ms 91172 KB Output is correct
24 Correct 1453 ms 98472 KB Output is correct
25 Correct 1488 ms 105648 KB Output is correct