oj.uz

Submission #171005

# Submission time Handle Problem Language Result Execution time Memory
171005 2019-12-27T02:47:54 Z super_j6 Simple game (IZhO17_game) C++14
0 / 100
 6 ms 4220 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];
			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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4188 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Incorrect 6 ms 4216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4188 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Incorrect 6 ms 4216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4188 KB Output is correct
2 Correct 6 ms 4220 KB Output is correct
3 Incorrect 6 ms 4216 KB Output isn't correct
4 Halted 0 ms 0 KB -