oj.uz

답안 #237823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237823 2020-06-08T23:47:45 Z LucaDantas Simple game (IZhO17_game) C++17
100 / 100
 100 ms 5240 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(a) ((int)(a).size())
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define trav(it, a) for(auto& it : a)
#define allin(it, a) for(auto it : a)
#define read(v, a, b) for(int i=(a); i<(b); i++) scanf("%d", &v[i]);
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define db(x) cerr << #x << " == " << x << endl

const int maxn = 1e6 + 100;

int bit[maxn];

void update(int x, int v) {
	for(; x < maxn; x += x&-x)
		bit[x] += v;
}

int query(int x) {
	int ans = 0;
	for(; x > 0; x -= x&-x)
		ans += bit[x];
	return ans;
}

int main(){
	int n, m; scanf("%d %d", &n, &m);
	vi a(n+1);
	read(a,1,n+1);
	rep(i,1,n) update(min(a[i], a[i+1]), 1), update(max(a[i], a[i+1])+1, -1);
	// It's in purpose not to include the last because there's no one in front of it
	while(m--) {
		int type, x; scanf("%d %d", &type, &x);
		if(type == 1) {
			int v; scanf("%d", &v);
			// if(n == 1) {
			// 	a[1] = v;
			// 	continue;
			// }
			int i = x;
			if(x == 1) {
				update(min(a[i], a[i+1]), -1), update(max(a[i], a[i+1])+1, 1);
				a[i] = v;
				update(min(a[i], a[i+1]), 1), update(max(a[i], a[i+1])+1, -1);
			}
			else if(x == n) {
				update(min(a[i], a[i-1]), -1), update(max(a[i], a[i-1])+1, 1);
				a[i] = v;
				update(min(a[i], a[i-1]), 1), update(max(a[i], a[i-1])+1, -1);
			}
			else {
				update(min(a[i], a[i+1]), -1), update(max(a[i], a[i+1])+1, 1);
				update(min(a[i], a[i-1]), -1), update(max(a[i], a[i-1])+1, 1);
				a[i] = v;
				update(min(a[i], a[i+1]), 1), update(max(a[i], a[i+1])+1, -1);
				update(min(a[i], a[i-1]), 1), update(max(a[i], a[i-1])+1, -1);
			}
		}
		else{
		// else if(n != 1){
			printf("%d\n", query(x));
		}
		// else {
		// 	if(x == a[1]) printf("1\n");
		// 	else printf("0\n");
		// }
	}
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:41:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m; scanf("%d %d", &n, &m);
            ~~~~~^~~~~~~~~~~~~~~~~
game.cpp:18:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define read(v, a, b) for(int i=(a); i<(b); i++) scanf("%d", &v[i]);
                                                  ~~~~~^~~~~~~~~~~~~
game.cpp:43:2: note: in expansion of macro 'read'
  read(a,1,n+1);
  ^~~~
game.cpp:47:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int type, x; scanf("%d %d", &type, &x);
                ~~~~~^~~~~~~~~~~~~~~~~~~~
game.cpp:49:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int v; scanf("%d", &v);
           ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 7 ms 3840 KB Output is correct
4 Correct 8 ms 3968 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 7 ms 3968 KB Output is correct
7 Correct 6 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 7 ms 3840 KB Output is correct
4 Correct 8 ms 3968 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 7 ms 3968 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 58 ms 992 KB Output is correct
9 Correct 69 ms 5240 KB Output is correct
10 Correct 72 ms 5240 KB Output is correct
11 Correct 58 ms 1016 KB Output is correct
12 Correct 70 ms 1432 KB Output is correct
13 Correct 60 ms 1400 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 7 ms 3840 KB Output is correct
4 Correct 8 ms 3968 KB Output is correct
5 Correct 7 ms 3840 KB Output is correct
6 Correct 7 ms 3968 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 58 ms 992 KB Output is correct
9 Correct 69 ms 5240 KB Output is correct
10 Correct 72 ms 5240 KB Output is correct
11 Correct 58 ms 1016 KB Output is correct
12 Correct 70 ms 1432 KB Output is correct
13 Correct 60 ms 1400 KB Output is correct
14 Correct 92 ms 4940 KB Output is correct
15 Correct 100 ms 4896 KB Output is correct
16 Correct 98 ms 5112 KB Output is correct
17 Correct 96 ms 5240 KB Output is correct
18 Correct 98 ms 5016 KB Output is correct