oj.uz

Submission #63359

# Submission time Handle Problem Language Result Execution time Memory
63359 2018-08-01T14:48:19 Z Tenuun Simple game (IZhO17_game) C++17
0 / 100
 8 ms 4532 KB 
#include<bits/stdc++.h>

using namespace std;

int tr[1000001];

void update(int ind, int val){
	while(ind<=1000001){
		tr[ind]+=val;
		ind+=ind&-ind;
	}
}

int get(int ind){
	int ans=0;
	while(ind){
		ans+=tr[ind];
		ind-=ind&-ind;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	memset(tr, 0, sizeof tr);
	int n, m, pos, val, t;
	cin >> n >> m;
	int a[n+1];
	for(int i=1; i<=n; i++){
		cin >> a[i];
		if(i>1){
			update(min(a[i], a[i-1]), 1);
			update(max(a[i], a[i-1]), -1);
		}
	}
	while(m--){
		cin >> t;
		if(t==1){
			cin >> pos >> val;
			if(pos>1){
				update(min(a[pos], a[pos-1]), -1);
				update(max(a[pos], a[pos-1])+1, 1);
			}
			if(pos+1<=n){
				update(min(a[pos], a[pos+1]), -1);
				update(max(a[pos], a[pos+1])+1, 1);
			}
			a[pos]=val;
			if(pos>1){
				update(min(a[pos], a[pos-1]), 1);
				update(max(a[pos], a[pos-1])+1, -1);
			}
			if(pos+1<=n){
				update(min(a[pos], a[pos+1]), 1);
				update(max(a[pos], a[pos+1])+1, -1);
			}
		}
		else{
			cin >> val;
			cout << get(val) << endl;
		}
	}
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4220 KB Output is correct
2 Correct 8 ms 4524 KB Output is correct
3 Incorrect 8 ms 4532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4220 KB Output is correct
2 Correct 8 ms 4524 KB Output is correct
3 Incorrect 8 ms 4532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4220 KB Output is correct
2 Correct 8 ms 4524 KB Output is correct
3 Incorrect 8 ms 4532 KB Output isn't correct
4 Halted 0 ms 0 KB -