Submission #503102

#	Time	Username	Problem	Language	Result	Execution time	Memory
503102		stefantaga	가로등 (APIO19_street_lamps)	C++14	0 / 100	83 ms	792 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
int v[300005],n,arb[1200005],q,x,y,ult[300005],nr[300005],i,j,t;

void update(int st,int dr,int nod,int poz,int val)
{
    if (st==dr)
    {
        arb[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if (poz<=mij)
    {
        update(st,mij,2*nod,poz,val);
    }
    else
    if (mij<poz)
    {
        update(mij+1,dr,2*nod+1,poz,val);
    }
    arb[nod]=max(arb[2*nod],arb[2*nod+1]);
}
int query(int st,int dr,int nod,int ua,int ub)
{
    if (dr<ua||ub<st)
    {
        return 0;
    }
    if (ua<=st&&dr<=ub)
    {
        return arb[nod];
    }
    int mij=(st+dr)/2;
    return max(query(st,mij,2*nod,ua,ub),query(mij+1,dr,2*nod+1,ua,ub));
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>q;
    for (i=1;i<=n;i++)
    {
        char ch;
        cin>>ch;
        v[i]=ch-'0';
        if (v[i]==1)
        {
            update(1,n,1,i,1);
        }
        else
        {
            update(1,n,1,i,1000000);
        }
    }
    for (i=1;i<=q;i++)
    {
        char tip[15];
        cin>>tip;
        if (strcmp(tip,"query")==0)
        {
            cin>>x>>y;
            int val=query(1,n,1,x,y);
            if (val<=q)
            {
                cout<<i-val+1<<'\n';
            }
            else
            {
                cout<<"0"<<'\n';
            }
        }
        else
        {
            cin>>x;
            update(1,n,1,x,i);
        }
    }
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20