Submission #129969

#	Time	Username	Problem	Language	Result	Execution time	Memory
129969		bvd	Street Lamps (APIO19_street_lamps)	C++14	20 / 100	2644 ms	171732 KiB

street_lamps

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 300000;
int n,q;
int a[maxn+1];
int f[maxn+1];

struct Node
{
    int value;
    int l,r;
    int leftNode,rightNode;
};
vector<Node> V;

int initIT(int x,int y)
{
    Node res;
    res.l = x;
    res.r = y;
    
    if (x==y)
        res.value = a[x];
    else
    {
        int m=(x+y)/2;
        int p1=initIT(x,m);
        int p2=initIT(m+1,y);
        res.leftNode = p1;
        res.rightNode = p2;
        res.value = V[p1].value+V[p2].value;
    }
    
    V.push_back(res);
    return V.size()-1;
}

int updateIT(int oldRoot,int x,int v)
{
    Node res;
    res.l = V[oldRoot].l;
    res.r = V[oldRoot].r;
    if (V[oldRoot].l==V[oldRoot].r)
    {
        res.value = v;
        V.push_back(res);
        return V.size()-1;
    }
    else
    {
        int leftNode = V[oldRoot].leftNode;
        int rightNode = V[oldRoot].rightNode;
        
        if (x<=V[leftNode].r)
        {
            res.leftNode = updateIT(leftNode,x,v);
            res.rightNode = rightNode;
            res.value = V[res.leftNode].value + V[res.rightNode].value;
        }
        else
        {
            res.leftNode = leftNode;
            res.rightNode = updateIT(rightNode,x,v);
            res.value = V[res.leftNode].value + V[res.rightNode].value;
        }

        V.push_back(res);
        return V.size()-1;
    }

}

int getIT(int i,int x,int y)
{
    int res = 0;
    
    if (y<V[i].l or x>V[i].r) res = 0;
    else
    if (x<=V[i].l and V[i].r<=y) res = V[i].value;
    else
    {
        int res1 = getIT(V[i].leftNode,x,y);
        int res2 = getIT(V[i].rightNode,x,y);
        res=res1+res2;
    }
    return res;
}

int root[maxn+1];


int main()
{
    ios_base::sync_with_stdio(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin >> n >> q;
    for (int i=1; i<=n; i++)
    {
        char c;
        cin >> c;
        a[i]=c-'0';
    }
    root[0] = initIT(1,n);

    //cout << getIT(root[0],1,5) << '\n';

    for (int i=1; i<=q; i++)
    {
        string op;
        cin >> op;
        root[i] = root[i-1];
        if (op[0]=='t')
        {
            int j;
            cin >> j;
            root[i] = updateIT(root[i-1],j,1);
        }
        else
        {
            int a,b;
            cin >> a >> b;
            b--;

            int dau=0,cuoi=i-1;
            do
            {
                int giua=(dau+cuoi)/2;
                if (getIT(root[giua],a,b)==b-a+1)
                    cuoi=giua-1;
                else
                    dau=giua+1;
            }
            while (dau<=cuoi);


            cout << i-dau << '\n';

        }
    }


    return 0;
}

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