oj.uz

Submission #892675

# Submission time Handle Problem Language Result Execution time Memory
892675 2023-12-25T16:41:33 Z maxFedorchuk Election (BOI18_election) C++14
100 / 100
 496 ms 44796 KB 
#include <bits/stdc++.h>
using namespace std;

struct strk
{
    long long frl;
    long long frr;
    long long riz;
    long long ans;
};

const long long MX=5e5+10;
strk mas[4*MX];

long long n,q;
string s;

strk mrg(strk a,strk b)
{
    strk rt;

    rt.frl=max(a.frl,b.frl+a.riz);
    rt.frr=max(b.frr,a.frr+b.riz);
    rt.riz=a.riz+b.riz;
    rt.ans=max({a.frl+b.frr,a.ans+b.riz,b.ans+a.riz});

    return rt;
}


void build(long long v,long long tl,long long tr)
{
    if(tl==tr)
    {
        if(s[tl]=='C')
        {
            mas[v]={0,0,-1,0};
        }
        else
        {
            mas[v]={1,1,1,1};
        }

        return;
    }

    long long mid=(tl+tr)/2;

    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);

    mas[v]=mrg(mas[v*2],mas[v*2+1]);

    return;
}

strk zap(long long v,long long tl,long long tr,long long l,long long r)
{
    if(r<tl || tr<l)
    {
        return {0,0,0,0};
    }

    if(l<=tl && tr<=r)
    {
        return mas[v];
    }

    long long mid=(tl+tr)/2;
    return mrg(zap(v*2,tl,mid,l,r),zap(v*2+1,mid+1,tr,l,r));
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>s>>q;
    s="*"+s;

    build(1,1,n);

    long long l,r;
    while(q--)
    {
        cin>>l>>r;
        cout<<zap(1,1,n,l,r).ans<<"\n";
    }

    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 46 ms 10064 KB Output is correct
7 Correct 44 ms 10408 KB Output is correct
8 Correct 45 ms 10064 KB Output is correct
9 Correct 40 ms 10072 KB Output is correct
10 Correct 53 ms 10060 KB Output is correct
11 Correct 45 ms 10264 KB Output is correct
12 Correct 45 ms 10064 KB Output is correct
13 Correct 45 ms 10316 KB Output is correct
14 Correct 51 ms 10060 KB Output is correct
15 Correct 48 ms 10220 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 46 ms 10064 KB Output is correct
7 Correct 44 ms 10408 KB Output is correct
8 Correct 45 ms 10064 KB Output is correct
9 Correct 40 ms 10072 KB Output is correct
10 Correct 53 ms 10060 KB Output is correct
11 Correct 45 ms 10264 KB Output is correct
12 Correct 45 ms 10064 KB Output is correct
13 Correct 45 ms 10316 KB Output is correct
14 Correct 51 ms 10060 KB Output is correct
15 Correct 48 ms 10220 KB Output is correct
16 Correct 489 ms 43928 KB Output is correct
17 Correct 379 ms 43148 KB Output is correct
18 Correct 406 ms 43420 KB Output is correct
19 Correct 353 ms 43000 KB Output is correct
20 Correct 443 ms 42744 KB Output is correct
21 Correct 496 ms 44436 KB Output is correct
22 Correct 459 ms 44472 KB Output is correct
23 Correct 449 ms 44796 KB Output is correct
24 Correct 442 ms 44380 KB Output is correct
25 Correct 472 ms 43772 KB Output is correct