oj.uz

Submission #38620

# Submission time Handle Problem Language Result Execution time Memory
38620 2018-01-05T06:23:26 Z MrPlany Simple game (IZhO17_game) C++14
22 / 100
 216 ms 6312 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int t[N+9],a[100100];
int n;

void add(int k, int val){
	while(k<N){
		t[k]+=val;
		k+=k&-k;
	}
}

void gosh(int a, int b, int val){
	if(a>b) swap(a,b);
	add(a,val);
	add(b+1,-val);
}

int sum(int pos){
	int s = 0;
	while(pos>0){
		s+=t[pos];
		pos-=pos&-pos;
	}
	return s;
}

int main(){
	
	cin>>n;
	
	int q;
	cin>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++) gosh(a[i],a[i+1],1);
	
	while(q--){
		
		int type;
		cin>>type;
		if(type==1){
			int pos, val;
			cin>>pos>>val;
			if(pos>1) gosh(a[pos-1],a[pos],-1);
			if(pos<n) gosh(a[pos],a[pos+1],-1);
			a[pos] = val;
			if(pos>1) gosh(a[pos-1],a[pos],1);
			if(pos<n) gosh(a[pos],a[pos+1],1);
		}
		else{
			int pos;
			cin>>pos;
			cout << sum(pos) << endl;
		}
		
	}
	
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Output is correct
2 Correct 6 ms 6312 KB Output is correct
3 Correct 16 ms 6312 KB Output is correct
4 Correct 3 ms 6312 KB Output is correct
5 Correct 9 ms 6312 KB Output is correct
6 Correct 0 ms 6312 KB Output is correct
7 Correct 9 ms 6312 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Output is correct
2 Correct 6 ms 6312 KB Output is correct
3 Correct 16 ms 6312 KB Output is correct
4 Correct 3 ms 6312 KB Output is correct
5 Correct 9 ms 6312 KB Output is correct
6 Correct 0 ms 6312 KB Output is correct
7 Correct 9 ms 6312 KB Output is correct
8 Correct 193 ms 6312 KB Output is correct
9 Runtime error 216 ms 6312 KB Execution timed out (wall clock limit exceeded)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6312 KB Output is correct
2 Correct 6 ms 6312 KB Output is correct
3 Correct 16 ms 6312 KB Output is correct
4 Correct 3 ms 6312 KB Output is correct
5 Correct 9 ms 6312 KB Output is correct
6 Correct 0 ms 6312 KB Output is correct
7 Correct 9 ms 6312 KB Output is correct
8 Correct 193 ms 6312 KB Output is correct
9 Runtime error 216 ms 6312 KB Execution timed out (wall clock limit exceeded)
10 Halted 0 ms 0 KB -