oj.uz

Submission #106278

# Submission time Handle Problem Language Result Execution time Memory
106278 2019-04-17T18:37:28 Z RedNextCentury Election (BOI18_election) C++14
100 / 100
 1368 ms 30216 KB 
#include<bits/stdc++.h>
using namespace std;
struct Q
{
    int l,r,id;
};
struct node
{
    int sum;
    int suf;
    node(){}
    node(int a,int b){sum=a,suf=b;}
};
node Merge(node a,node b)
{
    if (a.sum==1000000)return b;
    if (b.sum==1000000)return a;
    node ret;
    ret.sum=a.sum+b.sum;
    ret.suf = min(b.suf,b.sum+a.suf);
    return ret;
}
node tree[4000000];
int a[1000000];

#define mid (l+r)/2
#define L x*2
#define R x*2+1
void build(int x,int l,int r)
{
    if (l==r)
        tree[x]=node(a[l],min(a[l],0));
    else
    {
        build(L,l,mid);
        build(R,mid+1,r);
        tree[x]=Merge(tree[L],tree[R]);
    }
}
void upd(int x,int l,int r,int v,int val)
{
    if (v>r || v<l)return;
    if (l==r)
        tree[x]=node(val,min(val,0));
    else
    {
        upd(L,l,mid,v,val);
        upd(R,mid+1,r,v,val);
        tree[x]=Merge(tree[L],tree[R]);
    }
}
node query(int x,int l,int r,int s,int e)
{
    if (s>r || e<l)
        return node(1000000,0);
    if (l>=s && r<=e)
        return tree[x];
    return Merge(query(L,l,mid,s,e),query(R,mid+1,r,s,e));
}
bool operator<(Q a,Q b)
{
    return a.l>b.l;
}
Q q[1000000];
int ret[1000000];
int stk[1000000];
int sz=0;
int getLessThan(int v)
{
    int ret=sz;
    int l = 0, r=sz-1;
    while(l<=r)
    {
        if (stk[mid]<=v)
            ret=mid,r=mid-1;
        else
            l=mid+1;
    }
    return sz-ret;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    for (int i=1;i<=n;i++)
    {
        if (s[i-1]=='C')a[i]=1;
        else a[i]=-1;
    }
    int m;
    cin>>m;
    for (int i=0;i<m;i++)
    {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    build(1,1,n);
    sort(q,q+m);
    int l=n+1;
    for (int i=0;i<m;i++)
    {
        while(l>q[i].l)
        {
            l--;
            if (a[l]==-1)
            {
                stk[sz++] = l;
                upd(1,1,n,l,0);
            }
            else if (sz>0)
            {
                upd(1,1,n,stk[--sz],-1);
            }
        }
        ret[q[i].id] = getLessThan(q[i].r) - query(1,1,n,q[i].l,q[i].r).suf;
    }
    for (int i=0;i<m;i++)
        cout<<ret[i]<<endl;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 178 ms 5160 KB Output is correct
7 Correct 164 ms 5112 KB Output is correct
8 Correct 165 ms 5112 KB Output is correct
9 Correct 148 ms 5164 KB Output is correct
10 Correct 194 ms 5068 KB Output is correct
11 Correct 184 ms 5492 KB Output is correct
12 Correct 190 ms 5428 KB Output is correct
13 Correct 175 ms 5572 KB Output is correct
14 Correct 170 ms 5368 KB Output is correct
15 Correct 164 ms 5240 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 640 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 6 ms 512 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 178 ms 5160 KB Output is correct
7 Correct 164 ms 5112 KB Output is correct
8 Correct 165 ms 5112 KB Output is correct
9 Correct 148 ms 5164 KB Output is correct
10 Correct 194 ms 5068 KB Output is correct
11 Correct 184 ms 5492 KB Output is correct
12 Correct 190 ms 5428 KB Output is correct
13 Correct 175 ms 5572 KB Output is correct
14 Correct 170 ms 5368 KB Output is correct
15 Correct 164 ms 5240 KB Output is correct
16 Correct 1327 ms 28656 KB Output is correct
17 Correct 1127 ms 28264 KB Output is correct
18 Correct 1233 ms 28640 KB Output is correct
19 Correct 1368 ms 28128 KB Output is correct
20 Correct 1288 ms 27688 KB Output is correct
21 Correct 1341 ms 29996 KB Output is correct
22 Correct 1314 ms 29600 KB Output is correct
23 Correct 1312 ms 30216 KB Output is correct
24 Correct 1207 ms 29648 KB Output is correct
25 Correct 1126 ms 28860 KB Output is correct