oj.uz

Submission #68597

# Submission time Handle Problem Language Result Execution time Memory
68597 2018-08-17T13:07:31 Z renatsj Election (BOI18_election) C++14
100 / 100
 1381 ms 38816 KB 
#include<bits/stdc++.h>
using namespace std;
struct masivs{int l;int r;int poz;int rez;int maz;};
masivs q[500005];
struct segm{int l;int r;int rez;int sum;};
segm x[2000006];
int i,j,n,m,l,d,r,mas[500005],a[2],rez,maz,sum[500005],sk;
vector<int> k;
vector<int>::iterator it;
vector<int> del;
char c;
bool c1(masivs maz,masivs liel)
{
    if (maz.l==liel.l)
    {
        return maz.r>liel.r;
    }
    return maz.l>liel.l;
}
bool c2(masivs maz,masivs liel)
{
    return maz.poz<liel.poz;
}
int bins(int l,int r,int y)
{
    int c=l+(r-l)/2;
    /*if (l>r)
    {
        cout << l << " " << c << " " << r << "\n";
    }*/
    //cout << l << " " << c << " " << r << " " << del[c] << " " << y << "\n";
    if (l>=r)
    {
        return l;
    }
    if (del[c]>y)
    {
        return bins(c+1,r,y);
    }
    else
    {
        return bins(l,c,y);
    }
}
void build(int y,int l,int r)
{
    x[y].l=l;
    x[y].r=r;
    if (l!=r)
    {
        build(2*y+1,l,l+(r-l)/2);
        build(2*y+2,l+(r-l)/2+1,r);
        x[y].sum=x[2*y+1].sum+x[2*y+2].sum;
        x[y].rez=min(x[2*y+2].rez,x[2*y+1].rez+x[2*y+2].sum);
        //x[y].rez=min(min(x[2*y+1].rez,x[2*y+2].rez),x[y].sum);
    }
    else
    {
        x[y].rez=mas[l];
        x[y].sum=mas[l];
    }
    //cout << y << " " << l << " " << r << " " << x[y].rez << "\n";
}
void mod(int y,int g)
{
    if (x[y].l!=x[y].r)
    {
        if (g<x[2*y+2].l)
        {
            mod(2*y+1,g);
        }
        else
        {
            mod(2*y+2,g);
        }
        x[y].sum=x[2*y+1].sum+x[2*y+2].sum;
        x[y].rez=min(x[2*y+2].rez,x[2*y+1].rez+x[2*y+2].sum);
    }
    else
    {
        if (x[y].sum==0)
        {
            x[y].sum=mas[x[y].l];
            x[y].rez=mas[x[y].l];
        }
        else
        {
            x[y].sum=0;
            x[y].rez=0;
        }
    }
}
int f(int y,int l,int r)
{
    //cout << x[y].l << " " << x[y].r << "  " << l << " " << r << " " << x[y].rez << "\n";
    if (x[y].l==x[y].r)
    {
        q[i].maz=min(q[i].maz,sk+x[y].rez);
        sk+=x[y].sum;
        return x[y].l;
    }
    if (r<=x[2*y+1].r)
    {
        return f(2*y+1,l,r);
    }
    if (r!=x[y].r)
    {
        return f(2*y+2,l,r);
    }
    if (l>x[y].l)
    {
        return f(2*y+2,l,r);
    }
    q[i].maz=min(q[i].maz,sk+x[y].rez);
    sk+=x[y].sum;
    //q[i].maz=min(q[i].maz,sk);
    return x[y].l;
}
int main()
{
    //freopen("2-elections.in","r",stdin);
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    i=0;
    while (i<n)
    {
        cin >> c;
        if (c=='C')
        {
            mas[i]=1;
        }
        else
        {
            mas[i]=-1;
        }
        i++;
    }
    i=n-1;
    while (i>=0)
    {
        sum[i]=sum[i+1]+mas[i];
        i--;
    }
    cin >> m;
    i=0;
    while (i<m)
    {
        cin >> q[i].l >> q[i].r;
        q[i].l--;
        q[i].r--;
        q[i].poz=i;
        i++;
    }
    sort(q,q+m,c1);
    build(0,0,n-1);
    j=n-1;
    i=0;
    while (i<m)
    {
        while (j>=0&&j>=q[i].l)
        {
            if (mas[j]==-1)
            {
                del.push_back(j);
                mod(0,j);
            }
            else if (!del.empty())
            {
                mod(0,del.back());
                del.pop_back();
            }
            j--;
        }
        if (!del.empty())
        {
            q[i].rez=del.size()-bins(0,del.size()-1,q[i].r);
            if (-q[i].rez+del.size()>=0&&del[-q[i].rez+del.size()]>q[i].r)
            {
                q[i].rez--;
            }
        }
        d=q[i].r;
        sk=0;
        while (d>=q[i].l)
        {
            d=f(0,q[i].l,d)-1;
        }
        //cout << q[i].rez << " " << q[i].maz << "\n";
        i++;
    }
    sort(q,q+m,c2);
    i=0;
    while (i<m)
    {
        cout << q[i].rez-q[i].maz << "\n";
        i++;
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 5 ms 612 KB Output is correct
5 Correct 5 ms 628 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 5 ms 612 KB Output is correct
5 Correct 5 ms 628 KB Output is correct
6 Correct 138 ms 6928 KB Output is correct
7 Correct 129 ms 7908 KB Output is correct
8 Correct 145 ms 8720 KB Output is correct
9 Correct 114 ms 9744 KB Output is correct
10 Correct 137 ms 10740 KB Output is correct
11 Correct 142 ms 11580 KB Output is correct
12 Correct 181 ms 11580 KB Output is correct
13 Correct 130 ms 11692 KB Output is correct
14 Correct 158 ms 11692 KB Output is correct
15 Correct 137 ms 11692 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 5 ms 612 KB Output is correct
5 Correct 5 ms 628 KB Output is correct
6 Correct 138 ms 6928 KB Output is correct
7 Correct 129 ms 7908 KB Output is correct
8 Correct 145 ms 8720 KB Output is correct
9 Correct 114 ms 9744 KB Output is correct
10 Correct 137 ms 10740 KB Output is correct
11 Correct 142 ms 11580 KB Output is correct
12 Correct 181 ms 11580 KB Output is correct
13 Correct 130 ms 11692 KB Output is correct
14 Correct 158 ms 11692 KB Output is correct
15 Correct 137 ms 11692 KB Output is correct
16 Correct 1203 ms 37208 KB Output is correct
17 Correct 1276 ms 37268 KB Output is correct
18 Correct 1135 ms 37296 KB Output is correct
19 Correct 919 ms 37296 KB Output is correct
20 Correct 1283 ms 37296 KB Output is correct
21 Correct 1381 ms 38560 KB Output is correct
22 Correct 1343 ms 38560 KB Output is correct
23 Correct 1235 ms 38816 KB Output is correct
24 Correct 1165 ms 38816 KB Output is correct
25 Correct 1101 ms 38816 KB Output is correct