oj.uz

Submission #344372

# Submission time Handle Problem Language Result Execution time Memory
344372 2021-01-05T14:49:42 Z nicolaalexandra Weighting stones (IZhO11_stones) C++14
100 / 100
 324 ms 4648 KB 
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

struct segment_tree{
    int mini,maxi,lazy;
} aint[DIM*4];

int n,x,nr,i;

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].mini += aint[nod].lazy;
        aint[fiu_st].maxi += aint[nod].lazy;
        aint[fiu_st].lazy += aint[nod].lazy;

        aint[fiu_dr].mini += aint[nod].lazy;
        aint[fiu_dr].maxi += 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].maxi += val;
        aint[nod].mini += 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].mini = min (aint[nod<<1].mini,aint[(nod<<1)|1].mini);
    aint[nod].maxi = max (aint[nod<<1].maxi,aint[(nod<<1)|1].maxi);
}

int main (){

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

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>x>>nr;
        if (nr == 1)
            update (1,1,n,1,x,1);
        else update (1,1,n,1,x,-1);

        if (aint[1].mini >= 0)
            cout<<">\n";
        else {
            if (aint[1].maxi <= 0)
                cout<<"<\n";
            else cout<<"?\n";
        }
    }


    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 3 ms 364 KB Output is correct
8 Correct 4 ms 364 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 29 ms 748 KB Output is correct
11 Correct 187 ms 2412 KB Output is correct
12 Correct 309 ms 4460 KB Output is correct
13 Correct 316 ms 4460 KB Output is correct
14 Correct 323 ms 4648 KB Output is correct
15 Correct 319 ms 4332 KB Output is correct
16 Correct 324 ms 4460 KB Output is correct
17 Correct 317 ms 4376 KB Output is correct
18 Correct 322 ms 4460 KB Output is correct
19 Correct 322 ms 4460 KB Output is correct
20 Correct 319 ms 4460 KB Output is correct
21 Correct 317 ms 4460 KB Output is correct
22 Correct 323 ms 4588 KB Output is correct
23 Correct 321 ms 4460 KB Output is correct
24 Correct 320 ms 4332 KB Output is correct
25 Correct 319 ms 4588 KB Output is correct