oj.uz

Submission #36251

# Submission time Handle Problem Language Result Execution time Memory
36251 2017-12-06T14:02:48 Z touristk2000 Simple game (IZhO17_game) C++14
100 / 100
 506 ms 41076 KB 
#include <bits/stdc++.h>
#define N 1111111
#define debug(x) cout << #x <<  ' ' << x << endl;
using namespace std;
int t[N << 2], tt[N << 2];
void push (int v) {
	if (tt[v]){
		t[v*2] += tt[v];
		t[v*2+1] += tt[v];
		tt[v << 1] += tt[v];
		tt[v << 1 | 1] += tt[v];
		tt[v] = 0;
	}
}
void update (int v, int tl, int tr, int l, int r, int color) {
	if (l > r)
		return;
	if (l == tl && tr == r){
		t[v] += color;
		tt[v] += color;
	}
	else {
		push (v);
		int tm = (tl + tr) / 2;
		update (v*2, tl, tm, l, min(r,tm), color);
		update (v*2+1, tm+1, tr, max(l,tm+1), r, color);
		t[v] = t[v << 1] + t[v << 1 | 1];
	}
}
 
int get (int v, int tl, int tr, int pos) {
	if (tl == tr)
		return t[v];
	push (v);
	int tm = (tl + tr) / 2;
	if (pos <= tm)
		return get (v*2, tl, tm, pos);
	else
		return get (v*2+1, tm+1, tr, pos);
}
int n, a[N], m;
int main(){
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    scanf("%d%d%d", &n, &m, &a[1]);
    for(int i = 2; i <= n; i ++){
        scanf("%d", a + i);
        update(1, 1, N, min(a[i - 1], a[i]), max(a[i - 1], a[i]), 1);
    }
    while(m --){
        int t, p;
        scanf("%d%d",&t,&p);
        if(t == 1){
            int v;
            scanf("%d", &v);
            if(p > 1){
                update(1, 1, N, min(a[p - 1], a[p]), max(a[p - 1], a[p]), -1);
                update(1, 1, N, min(a[p - 1], v), max(a[p - 1], v), 1);
            }
            if(p < n){
                update(1, 1, N, min(a[p + 1], a[p]), max(a[p + 1], a[p]), -1);
                update(1, 1, N, min(a[p + 1], v), max(a[p + 1], v), 1);
            }
            a[p] = v;
        }
        else
            printf("%d\n", get(1, 1, N, p));
    }
    return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:45:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &a[1]);
                                   ^
game.cpp:47:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
                           ^
game.cpp:52:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&t,&p);
                            ^
game.cpp:55:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &v);
                            ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41076 KB Output is correct
2 Correct 9 ms 41076 KB Output is correct
3 Correct 3 ms 41076 KB Output is correct
4 Correct 6 ms 41076 KB Output is correct
5 Correct 6 ms 41076 KB Output is correct
6 Correct 0 ms 41076 KB Output is correct
7 Correct 3 ms 41076 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41076 KB Output is correct
2 Correct 9 ms 41076 KB Output is correct
3 Correct 3 ms 41076 KB Output is correct
4 Correct 6 ms 41076 KB Output is correct
5 Correct 6 ms 41076 KB Output is correct
6 Correct 0 ms 41076 KB Output is correct
7 Correct 3 ms 41076 KB Output is correct
8 Correct 86 ms 41076 KB Output is correct
9 Correct 249 ms 41076 KB Output is correct
10 Correct 259 ms 41076 KB Output is correct
11 Correct 89 ms 41076 KB Output is correct
12 Correct 136 ms 41076 KB Output is correct
13 Correct 143 ms 41076 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 41076 KB Output is correct
2 Correct 9 ms 41076 KB Output is correct
3 Correct 3 ms 41076 KB Output is correct
4 Correct 6 ms 41076 KB Output is correct
5 Correct 6 ms 41076 KB Output is correct
6 Correct 0 ms 41076 KB Output is correct
7 Correct 3 ms 41076 KB Output is correct
8 Correct 86 ms 41076 KB Output is correct
9 Correct 249 ms 41076 KB Output is correct
10 Correct 259 ms 41076 KB Output is correct
11 Correct 89 ms 41076 KB Output is correct
12 Correct 136 ms 41076 KB Output is correct
13 Correct 143 ms 41076 KB Output is correct
14 Correct 473 ms 41076 KB Output is correct
15 Correct 503 ms 41076 KB Output is correct
16 Correct 506 ms 41076 KB Output is correct
17 Correct 469 ms 41076 KB Output is correct
18 Correct 473 ms 41076 KB Output is correct