oj.uz

Submission #501726

# Submission time Handle Problem Language Result Execution time Memory
501726 2022-01-04T12:04:51 Z Aktan Simple game (IZhO17_game) C++17
100 / 100
 342 ms 19752 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define ft first
#define sc second
using namespace std;
const int mod=1e9+7,INF=1e17;
const int N = 1e6 + 5;
int d[4 * N];
int a[N];
void add(int l,int r,int v, int x, int lx,int rx){
	if(l>=rx || lx>=r){
		return;
	}
	if(lx>=l && rx<=r){
		d[x]+=v;
		return;
	}
	int m=(lx+rx)/2;
	add(l,r,v,x*2+1,lx,m);
	add(l,r,v,x*2+2,m,rx);
}
void del(int l,int r,int v, int x, int lx,int rx){
	if(l>=rx || lx>=r){
		return;
	}
	if(lx>=l && rx<=r){
		d[x]-=v;
		return;
	}
	int m=(lx+rx)/2;
	del(l,r,v,x*2+1,lx,m);
	del(l,r,v,x*2+2,m,rx);
}
long long get(int i,int x,int lx,int rx){
	if(rx-lx==1){
		return d[x];
	}
	int m=(lx+rx)/2;
	if(i<m){
		return get(i,x*2+1,lx,m)+d[x];
	}
	else{
		return get(i,x*2+2,m,rx)+d[x];
	}
}
main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++){
    	cin >> a[i];
    	if(i==0){
    		continue;
		}
		int l=min(a[i-1],a[i]);
		int r=max(a[i-1],a[i]);
		add(l,r,1,0,0,N);
	}
    for(int i=0;i<m;i++){
    	int type;
    	cin >> type;
    	if(type==1){
    		int pos,val;
    		cin >> pos >> val;
    		pos--;
    		if(pos>0){
    		int l1=min(a[pos-1],a[pos]);
		    int r1=max(a[pos-1],a[pos]);
    		del(l1,r1,1,0,0,N);
			}
			if(pos<n-1){
    		int l1=min(a[pos+1],a[pos]);
		    int r1=max(a[pos+1],a[pos]);
    		del(l1,r1,1,0,0,N);
			}
			a[pos]=val;
			if(pos>0){
			int l1=min(a[pos-1],a[pos]);
		    int r1=max(a[pos-1],a[pos]);
		    add(l1,r1,1,0,0,N);
			}
			if(pos<n-1){
			int l1=min(a[pos+1],a[pos]);
		    int r1=max(a[pos+1],a[pos]);
		    add(l1,r1,1,0,0,N);
			}
		}
		else{
			long long k;
			cin >> k;
			k--;
			cout << get(k,0,0,N) << endl;
		}
		
	}
}

Compilation message

game.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 9012 KB Output is correct
3 Correct 7 ms 8752 KB Output is correct
4 Correct 9 ms 9032 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 8 ms 8844 KB Output is correct
7 Correct 4 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 9012 KB Output is correct
3 Correct 7 ms 8752 KB Output is correct
4 Correct 9 ms 9032 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 8 ms 8844 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 190 ms 2120 KB Output is correct
9 Correct 288 ms 19652 KB Output is correct
10 Correct 268 ms 19668 KB Output is correct
11 Correct 175 ms 1872 KB Output is correct
12 Correct 223 ms 3616 KB Output is correct
13 Correct 227 ms 3204 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 7 ms 9012 KB Output is correct
3 Correct 7 ms 8752 KB Output is correct
4 Correct 9 ms 9032 KB Output is correct
5 Correct 7 ms 8908 KB Output is correct
6 Correct 8 ms 8844 KB Output is correct
7 Correct 4 ms 332 KB Output is correct
8 Correct 190 ms 2120 KB Output is correct
9 Correct 288 ms 19652 KB Output is correct
10 Correct 268 ms 19668 KB Output is correct
11 Correct 175 ms 1872 KB Output is correct
12 Correct 223 ms 3616 KB Output is correct
13 Correct 227 ms 3204 KB Output is correct
14 Correct 336 ms 19712 KB Output is correct
15 Correct 299 ms 19712 KB Output is correct
16 Correct 342 ms 19608 KB Output is correct
17 Correct 300 ms 19752 KB Output is correct
18 Correct 298 ms 19712 KB Output is correct