답안 #68590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
68590 2018-08-17T12:44:13 Z renatsj Election (BOI18_election) C++14
0 / 100
4 ms 504 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;
    //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 (l==r)
    {
        q[i].maz=min(q[i].maz,x[y].rez);
        return 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 l;
}
int main()
{
    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--;
        }
        q[i].rez=del.size()-bins(0,del.size()-1,q[i].r);
        if (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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -