oj.uz

Submission #129969

# Submission time Handle Problem Language Result Execution time Memory
129969 2019-07-13T16:49:20 Z bvd Street Lamps (APIO19_street_lamps) C++14
20 / 100
 2644 ms 171732 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 778 ms 44656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 4 ms 856 KB Output is correct
3 Correct 5 ms 728 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 769 ms 167200 KB Output is correct
6 Correct 1853 ms 171732 KB Output is correct
7 Correct 2535 ms 88480 KB Output is correct
8 Correct 2531 ms 22736 KB Output is correct
9 Correct 1028 ms 5244 KB Output is correct
10 Correct 1125 ms 5624 KB Output is correct
11 Correct 1137 ms 5716 KB Output is correct
12 Correct 2644 ms 22732 KB Output is correct
13 Correct 2584 ms 22732 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Incorrect 6 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -