oj.uz

Submission #888431

# Submission time Handle Problem Language Result Execution time Memory
888431 2023-12-17T11:46:07 Z pcc Simple game (IZhO17_game) C++14
100 / 100
 49 ms 9000 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e6+10;
int n,q;
int arr[mxn];
int bit[mxn];

void modify(int p,int v){
	for(;p<mxn;p+=p&-p)bit[p] += v;
	return;
}
int getval(int p){
	int re = 0;
	for(;p>0;p-= p&-p)re += bit[p];
	return re;
}

void add(int l,int r){
	if(r<l)swap(l,r);
	modify(l,1);
	modify(r+1,-1);
}
void del(int l,int r){
	if(r<l)swap(l,r);
	modify(l,-1);
	modify(r+1,1);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1;i<=n;i++)cin>>arr[i];
	for(int i = 2;i<=n;i++){
		add(arr[i-1],arr[i]);
	}
	while(q--){
		int t;
		cin>>t;
		if(t == 1){
			int p,v;
			cin>>p>>v;
			if(p != 1)del(arr[p-1],arr[p]);
			if(p != n)del(arr[p],arr[p+1]);
			arr[p] = v;
			if(p != n)add(arr[p],arr[p+1]);
			if(p != 1)add(arr[p],arr[p-1]);
		}
		else{
			int p;
			cin>>p;
			cout<<getval(p)<<'\n';
		}
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 31 ms 7868 KB Output is correct
9 Correct 31 ms 8792 KB Output is correct
10 Correct 31 ms 8784 KB Output is correct
11 Correct 28 ms 7516 KB Output is correct
12 Correct 28 ms 8532 KB Output is correct
13 Correct 29 ms 8544 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 31 ms 7868 KB Output is correct
9 Correct 31 ms 8792 KB Output is correct
10 Correct 31 ms 8784 KB Output is correct
11 Correct 28 ms 7516 KB Output is correct
12 Correct 28 ms 8532 KB Output is correct
13 Correct 29 ms 8544 KB Output is correct
14 Correct 40 ms 9000 KB Output is correct
15 Correct 49 ms 8788 KB Output is correct
16 Correct 42 ms 8788 KB Output is correct
17 Correct 39 ms 8952 KB Output is correct
18 Correct 42 ms 8800 KB Output is correct