oj.uz

Submission #750548

# Submission time Handle Problem Language Result Execution time Memory
750548 2023-05-29T16:55:19 Z amin Election (BOI18_election) C++14
100 / 100
 1189 ms 37808 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
int sum[2500000];
int seg[2500000];
int segl[2500000];
int segr[2500000];
int a[2000000];
int z;
void merg(int v,int v1,int v2)
{

    sum[v]=sum[v1]+sum[v2];

    segl[v]=segl[v1]+max(0,segl[v2]-segl[v1]-sum[v1]);
    segr[v]=segr[v2]+max(0,segr[v1]-segr[v2]-sum[v2]);
   // segr[v]=max(segr[v1],segr[v2]);
    int add1=sum[v1]+segl[v1]+max(0,seg[v1]-segl[v1]-(sum[v2]+segr[v2]));
    seg[v]=segl[v1]+segr[v2]+max(0,seg[v1]-segl[v1]-(sum[v2]+segr[v2]))+max(0,seg[v2]-segr[v2]-add1);


}
void build(int v,int tl,int tr)
{
    if(tl==tr)
    {
        if(a[tl]==1)
        {
        sum[v]=1;
        segl[v]=0;
        segr[v]=0;
        seg[v]=0;
        }else
        {
        sum[v]=-1;
        segl[v]=1;
        segr[v]=1;
        seg[v]=1;
        }
        return ;
    }
    int tm=(tl+tr)/2;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
    merg(v,v*2,v*2+1);
 //   cout<<tl<<' '<<tr<<' '<<seg[v]<<' '<<segl[v]<<' '<<segr[v]<<endl;
}
void ans(int v,int tl,int tr,int l,int r)
{
    if(l>r)
        return ;
    if(tl==l&&tr==r)
    {
      //   cout<<tl<<' '<<tr<<' '<<seg[z]<<endl;
        merg(z+1,z,v);
        seg[z]=seg[z+1];
        segl[z]=segl[z+1];
        segr[z]=segr[z+1];
        sum[z]=sum[z+1];
        // cout<<tl<<' '<<tr<<' '<<seg[z]<<endl;

        return ;
    }
    int tm=(tl+tr)/2;
    ans(v*2,tl,tm,l,min(r,tm));
    ans(v*2+1,tm+1,tr,max(l,tm+1),r);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  int n;
  cin>>n;
 char c[n];
 for(int i=0;i<n;i++)
 {
     cin>>c[i];
     if(c[i]=='T')
        a[i]=-1;
     else
        a[i]=1;
 }
 build(1,0,n-1);
 int q;
 cin>>q;
 while(q--)
 {
     int x,y;
     cin>>x>>y;
     x--;
     y--;
     z=n*4+1+q;

   seg[z+1]=  seg[z]=0;
   segl[z+1]=  segl[z]=0;
     segl[z+1]=segr[z]=0;
   sum[z+1]  =sum[z]=0;

ans(1,0,n-1,x,y);
     cout<<seg[z]<<endl;
 }

}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 133 ms 6112 KB Output is correct
7 Correct 151 ms 6144 KB Output is correct
8 Correct 130 ms 6004 KB Output is correct
9 Correct 119 ms 6100 KB Output is correct
10 Correct 134 ms 6036 KB Output is correct
11 Correct 142 ms 6140 KB Output is correct
12 Correct 123 ms 6148 KB Output is correct
13 Correct 133 ms 6148 KB Output is correct
14 Correct 139 ms 6204 KB Output is correct
15 Correct 128 ms 6096 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 472 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 133 ms 6112 KB Output is correct
7 Correct 151 ms 6144 KB Output is correct
8 Correct 130 ms 6004 KB Output is correct
9 Correct 119 ms 6100 KB Output is correct
10 Correct 134 ms 6036 KB Output is correct
11 Correct 142 ms 6140 KB Output is correct
12 Correct 123 ms 6148 KB Output is correct
13 Correct 133 ms 6148 KB Output is correct
14 Correct 139 ms 6204 KB Output is correct
15 Correct 128 ms 6096 KB Output is correct
16 Correct 1133 ms 35892 KB Output is correct
17 Correct 1035 ms 36412 KB Output is correct
18 Correct 1059 ms 36600 KB Output is correct
19 Correct 956 ms 35988 KB Output is correct
20 Correct 1189 ms 36008 KB Output is correct
21 Correct 1131 ms 37552 KB Output is correct
22 Correct 1078 ms 37440 KB Output is correct
23 Correct 1083 ms 37808 KB Output is correct
24 Correct 1115 ms 37252 KB Output is correct
25 Correct 1076 ms 36888 KB Output is correct