oj.uz

Submission #366542

# Submission time Handle Problem Language Result Execution time Memory
366542 2021-02-14T11:26:42 Z nicolaalexandra Simple game (IZhO17_game) C++14
100 / 100
 804 ms 19788 KB 
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

struct segment_tree{
    int sum,lazy;
} aint[DIM*40];

int n,m,i,j,x,y,poz,val,q,tip;
int v[DIM];



void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        aint[fiu_st].sum += aint[nod].lazy;
        aint[fiu_st].lazy += aint[nod].lazy;

        aint[fiu_dr].sum += aint[nod].lazy;
        aint[fiu_dr].lazy += aint[nod].lazy;
    }
    aint[nod].lazy = 0;
}

void update (int nod, int st, int dr, int x, int y, int val){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].sum += val;
        aint[nod].lazy += val;
        update_lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);

    update_lazy (nod<<1,st,mid);
    update_lazy ((nod<<1)|1,mid+1,dr);

    aint[nod].sum = aint[(nod<<1)].sum + aint[(nod<<1)|1].sum;
}

int query (int nod, int st, int dr, int poz){
    update_lazy(nod,st,dr);
    if (st == dr)
        return aint[nod].sum;
    int mid = (st+dr)>>1;
    if (poz <= mid)
        return query (nod<<1,st,mid,poz);
    else return query ((nod<<1)|1,mid+1,dr,poz);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>q;
    for (i=1;i<=n;i++)
        cin>>v[i];

    m = 1000000;
    //m = 7;


    for (i=1;i<n;i++){
        int x = v[i], y = v[i+1];

        if (x > y)
            swap (x,y);

        update (1,1,m,x,y,1);
    }

    for (i=2;i<n;i++)
        update (1,1,m,v[i],v[i],-1);



    for (;q--;){
        cin>>tip;
        if (tip == 1){
            cin>>poz>>val;

            if (poz > 1){
                int x = v[poz-1], y = v[poz];
                if (x > y)
                    swap (x,y);
                update (1,1,m,x,y,-1);
            }
            if (poz < n){
                int x = v[poz], y = v[poz+1];
                if (x > y)
                    swap (x,y);
                update (1,1,m,x,y,-1);
            }

            if (poz > 1 && poz < n)
                update (1,1,m,v[poz],v[poz],1);

            v[poz] = val;


            if (poz > 1){
                int x = v[poz-1], y = v[poz];
                if (x > y)
                    swap (x,y);
                update (1,1,m,x,y,1);
            }
            if (poz < n){
                int x = v[poz], y = v[poz+1];
                if (x > y)
                    swap (x,y);
                update (1,1,m,x,y,1);
            }

            if (poz > 1 && poz < n)
                update (1,1,m,v[poz],v[poz],-1);
        } else {
            cin>>poz;
            cout<<query(1,1,m,poz)<<"\n";
        }
    }


    return 0;
}/// copy paste ioit

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 13036 KB Output is correct
3 Correct 15 ms 12796 KB Output is correct
4 Correct 15 ms 13036 KB Output is correct
5 Correct 15 ms 12908 KB Output is correct
6 Correct 15 ms 13164 KB Output is correct
7 Correct 10 ms 9708 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 13036 KB Output is correct
3 Correct 15 ms 12796 KB Output is correct
4 Correct 15 ms 13036 KB Output is correct
5 Correct 15 ms 12908 KB Output is correct
6 Correct 15 ms 13164 KB Output is correct
7 Correct 10 ms 9708 KB Output is correct
8 Correct 376 ms 1892 KB Output is correct
9 Correct 573 ms 19672 KB Output is correct
10 Correct 571 ms 19436 KB Output is correct
11 Correct 365 ms 1736 KB Output is correct
12 Correct 466 ms 3308 KB Output is correct
13 Correct 397 ms 19272 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 16 ms 13036 KB Output is correct
3 Correct 15 ms 12796 KB Output is correct
4 Correct 15 ms 13036 KB Output is correct
5 Correct 15 ms 12908 KB Output is correct
6 Correct 15 ms 13164 KB Output is correct
7 Correct 10 ms 9708 KB Output is correct
8 Correct 376 ms 1892 KB Output is correct
9 Correct 573 ms 19672 KB Output is correct
10 Correct 571 ms 19436 KB Output is correct
11 Correct 365 ms 1736 KB Output is correct
12 Correct 466 ms 3308 KB Output is correct
13 Correct 397 ms 19272 KB Output is correct
14 Correct 787 ms 19528 KB Output is correct
15 Correct 799 ms 19564 KB Output is correct
16 Correct 804 ms 19788 KB Output is correct
17 Correct 796 ms 19436 KB Output is correct
18 Correct 802 ms 19436 KB Output is correct