oj.uz

Submission #855801

# Submission time Handle Problem Language Result Execution time Memory
855801 2023-10-01T20:36:02 Z ivaziva Election (BOI18_election) C++14
100 / 100
 1206 ms 44376 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 500010

long long n;
long long q;
string s;
pair<pair<long long,long long>,pair<long long,long long>> seg[MAXN*4];

void build(long long node,long long l,long long r)
{
    if (l==r)
    {
        if (s[l-1]=='T') seg[node]={{1,1},{1,1}};
        else seg[node]={{0,0},{-1,0}};
    }
    else
    {
        long long mid=(l+r)/2;
        build(2*node,l,mid);
        build(2*node+1,mid+1,r);
        seg[node].first.first=max(seg[2*node].first.first,seg[2*node].second.first+seg[2*node+1].first.first);
        seg[node].first.second=max(seg[2*node].first.second+seg[2*node+1].second.first,seg[2*node+1].first.second);
        seg[node].second.first=seg[2*node].second.first+seg[2*node+1].second.first;
        seg[node].second.second=max(max(seg[2*node].second.second+seg[2*node+1].second.first,seg[2*node].second.first+seg[2*node+1].second.second),seg[2*node].first.first+seg[2*node+1].first.second);
    }
}

pair<pair<long long,long long>,pair<long long,long long>> sol(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return {{0,0},{0,0}};
    if (l==a and r==b) return seg[node];
    long long mid=(l+r)/2;
    pair<pair<long long,long long>,pair<long long,long long>> val1=sol(2*node,l,mid,a,min(b,mid));
    pair<pair<long long,long long>,pair<long long,long long>> val2=sol(2*node+1,mid+1,r,max(a,mid+1),b);
    pair<pair<long long,long long>,pair<long long,long long>> val;
    val.first.first=max(val1.first.first,val1.second.first+val2.first.first);
    val.first.second=max(val1.first.second+val2.second.first,val2.first.second);
    val.second.first=val1.second.first+val2.second.first;
    val.second.second=max(max(val1.second.second+val2.second.first,val1.second.first+val2.second.second),val1.first.first+val2.first.second);
    return val;
}

int main()
{
    cin>>n>>s;
    build(1,1,n);
    cin>>q;
    for (long long i=1;i<=q;i++)
    {
        long long l,r;
        cin>>l>>r;
        cout<<sol(1,1,n,l,r).second.second<<endl;
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 146 ms 10168 KB Output is correct
7 Correct 135 ms 9916 KB Output is correct
8 Correct 137 ms 10068 KB Output is correct
9 Correct 133 ms 9896 KB Output is correct
10 Correct 141 ms 9904 KB Output is correct
11 Correct 180 ms 10068 KB Output is correct
12 Correct 142 ms 10064 KB Output is correct
13 Correct 147 ms 10580 KB Output is correct
14 Correct 138 ms 10260 KB Output is correct
15 Correct 144 ms 9992 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 146 ms 10168 KB Output is correct
7 Correct 135 ms 9916 KB Output is correct
8 Correct 137 ms 10068 KB Output is correct
9 Correct 133 ms 9896 KB Output is correct
10 Correct 141 ms 9904 KB Output is correct
11 Correct 180 ms 10068 KB Output is correct
12 Correct 142 ms 10064 KB Output is correct
13 Correct 147 ms 10580 KB Output is correct
14 Correct 138 ms 10260 KB Output is correct
15 Correct 144 ms 9992 KB Output is correct
16 Correct 1199 ms 43464 KB Output is correct
17 Correct 1032 ms 42968 KB Output is correct
18 Correct 1127 ms 43216 KB Output is correct
19 Correct 1027 ms 42752 KB Output is correct
20 Correct 1125 ms 42184 KB Output is correct
21 Correct 1130 ms 44376 KB Output is correct
22 Correct 1206 ms 44284 KB Output is correct
23 Correct 1191 ms 44024 KB Output is correct
24 Correct 1143 ms 43716 KB Output is correct
25 Correct 1147 ms 43188 KB Output is correct