oj.uz

Submission #74980

# Submission time Handle Problem Language Result Execution time Memory
74980 2018-09-07T20:44:56 Z Vardanyan Weighting stones (IZhO11_stones) C++14
100 / 100
 113 ms 15172 KB 
//#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
using namespace std;
const int N = 100*1000+7;
pair<int,int> t[4*N];
int f[4*N];
void push(int v, int s, int e) {
	if (f[v]) {
		t[v].first += (1*f[v]);
		t[v].second += (1*f[v]);
		if (s != e) {
			f[v*2] += f[v];
			f[v*2 + 1] += f[v];
		}
		f[v] = 0;
	}
}

void update(int v, int s, int e, int l, int r, int val) {
	push(v, s, e);
	if(l>r) return;
	if (s == l && e == r) {
		f[v] += val;
		push(v, s, e);
		return;
	}
	int m = (s + e) / 2;
	update(v*2, s, m, l, min(m,r), val);
	update(v*2 + 1, m + 1, e, max(l,m+1), r, val);
	push(v*2,s,m);
	push(v*2+1,m+1,e);
	t[v].first = max(t[v*2].first, t[v*2 + 1].first);
	t[v].second = min(t[v*2].second, t[v*2 + 1].second);
}

int main(){
    int n;
    scanf("%d",&n);

    for(int i = 1;i<=n;i++){
        int r,s;
        scanf("%d%d",&r,&s);
        if(s == 1) update(1,1,n,1,r,1);
        else update(1,1,n,1,r,-1);
        if(t[1].first>0 && t[1].second<0){
            printf("?\n");
            continue;
        }
        if(t[1].first>=0 && t[1].second>=0){
            printf(">\n");
            continue;
        }
        printf("<\n");
    }
    return 0;
}

Compilation message

stones.cpp: In function 'int main()':
stones.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
stones.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&r,&s);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 3 ms 648 KB Output is correct
9 Correct 3 ms 656 KB Output is correct
10 Correct 10 ms 1048 KB Output is correct
11 Correct 51 ms 2788 KB Output is correct
12 Correct 79 ms 5020 KB Output is correct
13 Correct 67 ms 5860 KB Output is correct
14 Correct 68 ms 6684 KB Output is correct
15 Correct 70 ms 7404 KB Output is correct
16 Correct 66 ms 8192 KB Output is correct
17 Correct 66 ms 8964 KB Output is correct
18 Correct 71 ms 9736 KB Output is correct
19 Correct 68 ms 10552 KB Output is correct
20 Correct 83 ms 11244 KB Output is correct
21 Correct 70 ms 12160 KB Output is correct
22 Correct 113 ms 13048 KB Output is correct
23 Correct 79 ms 13628 KB Output is correct
24 Correct 88 ms 14388 KB Output is correct
25 Correct 74 ms 15172 KB Output is correct