oj.uz

답안 #237822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
237822 2020-06-08T23:46:40 Z LucaDantas Simple game (IZhO17_game) C++17
100 / 100
 94 ms 6908 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 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 5 ms 384 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 7 ms 3968 KB Output is correct
4 Correct 7 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 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 7 ms 3968 KB Output is correct
4 Correct 7 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 5 ms 384 KB Output is correct
8 Correct 53 ms 1784 KB Output is correct
9 Correct 71 ms 6904 KB Output is correct
10 Correct 68 ms 6908 KB Output is correct
11 Correct 55 ms 1656 KB Output is correct
12 Correct 59 ms 2808 KB Output is correct
13 Correct 57 ms 2808 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 3840 KB Output is correct
3 Correct 7 ms 3968 KB Output is correct
4 Correct 7 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 5 ms 384 KB Output is correct
8 Correct 53 ms 1784 KB Output is correct
9 Correct 71 ms 6904 KB Output is correct
10 Correct 68 ms 6908 KB Output is correct
11 Correct 55 ms 1656 KB Output is correct
12 Correct 59 ms 2808 KB Output is correct
13 Correct 57 ms 2808 KB Output is correct
14 Correct 85 ms 6892 KB Output is correct
15 Correct 85 ms 6904 KB Output is correct
16 Correct 81 ms 6904 KB Output is correct
17 Correct 91 ms 6904 KB Output is correct
18 Correct 94 ms 6904 KB Output is correct