oj.uz

Submission #291387

# Submission time Handle Problem Language Result Execution time Memory
291387 2020-09-05T08:52:43 Z kshitij_sodani Simple game (IZhO17_game) C++14
0 / 100
 4 ms 3872 KB 
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
//#define endl '\n'
int n,m;
int it[100001];
int tree[1000001];
void u(int i,int j){
	while(i<1000001){
		tree[i]+=j;
		i+=(i&-i);
	}
}
int ss(int i){
	int su=0;
	while(i>0){
		su+=tree[i];
		i-=(i&-i);
	}
	return su;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	for(int i=0;i<n-1;i++){
		int aa=min(it[i],it[i+1]);
		int bb=max(it[i],it[i+1]);
		u(aa,1);
		u(bb,-1);
	}

	for(int ii=0;ii<m;ii++){
		int tt;
		cin>>tt;
		if(tt==1){
			int i,val;
			cin>>i>>val;
			i--;
			if(i>0){
				int aa=min(it[i],it[i-1]);
				int bb=max(it[i],it[i-1]);
				u(aa,-1);
				u(bb,1);
				it[i]=val;
				aa=min(it[i],it[i-1]);
				bb=max(it[i],it[i-1]);
				u(aa,1);
				u(bb,-1);
			}
			if(i<n-1){
				int aa=min(it[i],it[i+1]);
				int bb=max(it[i],it[i+1]);
				u(aa,-1);
				u(bb,1);
				it[i]=val;
				aa=min(it[i],it[i+1]);
				bb=max(it[i],it[i+1]);
				u(aa,1);
				u(bb,-1);
			}
		}
		else{
			int aa;
			cin>>aa;
			cout<<ss(aa)<<'\n';
		}
	}
	//








	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 4 ms 3872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 4 ms 3872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 4 ms 3872 KB Output isn't correct
3 Halted 0 ms 0 KB -