oj.uz

Submission #18444

# Submission time Handle Problem Language Result Execution time Memory
18444 2016-02-02T11:24:36 Z chan492811 Weighting stones (IZhO11_stones) C++
100 / 100
 76 ms 79208 KB 
#include <cstdio>
#include <algorithm>
using namespace std;
int n,tn=1;
struct data{
    int low,high,l,r,sum;
};
data tree[4000010];
void make_tree(int a){
    if(a>=tn) return;
    make_tree(a*2); make_tree(a*2+1);
    if(tree[a*2].r==0) return;
    if(tree[a*2+1].r==0){ tree[a]=tree[a*2]; return; }
    tree[a].l=tree[a*2].l; tree[a].r=tree[a*2+1].r;
}
void update(int a,int l,int r,int plus){
    if(tree[a].r<l || tree[a].l>r) return;
    if(tree[a].l>=l && tree[a].r<=r){ tree[a].sum+=plus,tree[a].low+=plus,tree[a].high+=plus; return; }
    update(a*2,l,r,plus); update(a*2+1,l,r,plus);
    if(tree[a*2+1].r==0){ tree[a].low=tree[a*2].low; tree[a].high=tree[a*2].high; }
    else { tree[a].low=min(tree[a*2].low,tree[a*2+1].low); tree[a].high=max(tree[a*2].high,tree[a*2+1].high); }
    tree[a].low+=tree[a].sum; tree[a].high+=tree[a].sum;
}
int main(){
    int i,a,s;
    scanf("%d",&n); while(tn<n) tn*=2;
    for(i=tn;i<tn+n;i++) tree[i].r=i-tn+1,tree[i].l=i-tn+1;
    make_tree(1);
    for(i=0;i<n;i++){
        scanf("%d %d",&a,&s);
        if(s==1) update(1,1,a,1);
        else update(1,1,a,-1);
        if(tree[1].low<0 && tree[1].high>0) printf("?\n");
        else if(tree[1].high>0) printf(">\n");
        else printf("<\n");
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 79208 KB Output is correct - 73 tokens
2 Correct 0 ms 79208 KB Output is correct - 89 tokens
3 Correct 0 ms 79208 KB Output is correct - 221 tokens
4 Correct 0 ms 79208 KB Output is correct - 21 tokens
5 Correct 0 ms 79208 KB Output is correct - 369 tokens
6 Correct 0 ms 79208 KB Output is correct - 492 tokens
7 Correct 0 ms 79208 KB Output is correct - 945 tokens
8 Correct 0 ms 79208 KB Output is correct - 1237 tokens
9 Correct 0 ms 79208 KB Output is correct - 1105 tokens
10 Correct 3 ms 79208 KB Output is correct - 8921 tokens
11 Correct 36 ms 79208 KB Output is correct - 56110 tokens
12 Correct 76 ms 79208 KB Output is correct - 90207 tokens
13 Correct 52 ms 79208 KB Output is correct - 100000 tokens
14 Correct 66 ms 79208 KB Output is correct - 100000 tokens
15 Correct 63 ms 79208 KB Output is correct - 100000 tokens
16 Correct 64 ms 79208 KB Output is correct - 100000 tokens
17 Correct 60 ms 79208 KB Output is correct - 100000 tokens
18 Correct 64 ms 79208 KB Output is correct - 99999 tokens
19 Correct 68 ms 79208 KB Output is correct - 99999 tokens
20 Correct 64 ms 79208 KB Output is correct - 99999 tokens
21 Correct 60 ms 79208 KB Output is correct - 100000 tokens
22 Correct 64 ms 79208 KB Output is correct - 100000 tokens
23 Correct 63 ms 79208 KB Output is correct - 100000 tokens
24 Correct 61 ms 79208 KB Output is correct - 100000 tokens
25 Correct 59 ms 79208 KB Output is correct - 100000 tokens