oj.uz

Submission #171006

# Submission time Handle Problem Language Result Execution time Memory
171006 2019-12-27T02:53:46 Z super_j6 Simple game (IZhO17_game) C++14
100 / 100
 88 ms 7032 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define endl '\n'
#define pi pair<int, int>

const int maxn = 1000001;
struct BIT{
	int bit[maxn];
	
	BIT(){
		memset(bit, 0, sizeof(bit));
	}
	
	void add(int x, int v){
		for(x++; x < maxn; x += x & -x) bit[x] += v;
	}
	
	void add(int a, int b, int v){
		if(a > b) swap(a, b);
		add(a, v);
		add(b + 1, -v);
	}
	
	int qry(int x){
		int ret = 0;
		for(x++; x; x -= x & -x) ret += bit[x];
		return ret;
	}
};

int n, m;
int a[maxn];
BIT bit;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
		if(i) bit.add(a[i - 1], a[i], 1);
	}
	
	for(int i = 0; i < m; i++){
		int t, x;
		cin >> t >> x;
		t--, x--;
		if(t){
			cout << bit.qry(x) << endl;
		}else{
			if(x) bit.add(a[x - 1], a[x], -1);
			if(x < n - 1) bit.add(a[x], a[x + 1], -1);
			cin >> a[x];
			a[x]--;
			if(x) bit.add(a[x - 1], a[x], 1);
			if(x < n - 1) bit.add(a[x], a[x + 1], 1);
		}
	}

	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4220 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4344 KB Output is correct
5 Correct 6 ms 4212 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 4344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4220 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4344 KB Output is correct
5 Correct 6 ms 4212 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 4344 KB Output is correct
8 Correct 49 ms 5724 KB Output is correct
9 Correct 57 ms 6952 KB Output is correct
10 Correct 57 ms 6904 KB Output is correct
11 Correct 49 ms 5624 KB Output is correct
12 Correct 53 ms 6728 KB Output is correct
13 Correct 57 ms 6776 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4220 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Correct 6 ms 4216 KB Output is correct
4 Correct 6 ms 4344 KB Output is correct
5 Correct 6 ms 4212 KB Output is correct
6 Correct 6 ms 4344 KB Output is correct
7 Correct 6 ms 4344 KB Output is correct
8 Correct 49 ms 5724 KB Output is correct
9 Correct 57 ms 6952 KB Output is correct
10 Correct 57 ms 6904 KB Output is correct
11 Correct 49 ms 5624 KB Output is correct
12 Correct 53 ms 6728 KB Output is correct
13 Correct 57 ms 6776 KB Output is correct
14 Correct 79 ms 7032 KB Output is correct
15 Correct 82 ms 6948 KB Output is correct
16 Correct 88 ms 6868 KB Output is correct
17 Correct 80 ms 6904 KB Output is correct
18 Correct 80 ms 7004 KB Output is correct