oj.uz

Submission #332750

# Submission time Handle Problem Language Result Execution time Memory
332750 2020-12-03T06:37:24 Z Bill_00 Simple game (IZhO17_game) C++14
100 / 100
 689 ms 27892 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;
int a[100001];
int lazy[5000001],value[5000001];
void update(int id,int l,int r,int L,int R,int d){
	if(L>R) return;
	value[id]+=lazy[id];
	lazy[id*2]+=lazy[id];
	lazy[id*2+1]+=lazy[id];
	lazy[id]=0;
	if(l>R || L>r){
		return;
	}
	if(L<=l && r<=R){
		value[id]+=d;
		lazy[id*2]+=d;
		lazy[id*2+1]+=d;
		return;
	}
	int m=l+r>>1;
	update(id*2,l,m,L,R,d);
	update(id*2+1,m+1,r,L,R,d);
	value[id]=value[id*2]+value[id*2+1];
}
int query(int id,int l,int r,int L,int R){
	value[id]+=lazy[id];
	lazy[id*2]+=lazy[id];
	lazy[id*2+1]+=lazy[id];
	lazy[id]=0;
	if(l>R || L>r){
		return 0;
	}
	if(L<=l && r<=R){
		return value[id];
	}
	int m=l+r>>1;
	return query(id*2,l,m,L,R)+query(id*2+1,m+1,r,L,R);
}
int main() {
	//ios_base::sync_with_stdio(NULL);
	// cin.tie(NULL);
	// cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	for(int i=1;i<n;i++){
		update(1,1,1000000,min(a[i],a[i+1]),max(a[i],a[i+1]),1);
	}
	for(int i=1;i<=m;i++){
		int type;
		cin >> type;
		if(type==1){
			int pos,val;
			cin >> pos >> val;
			if(pos!=1){
				update(1,1,1000000,min(a[pos-1],a[pos]),max(a[pos-1],a[pos]),-1);
				update(1,1,1000000,min(a[pos-1],val),max(a[pos-1],val),1);
			}
			if(pos!=n){
				update(1,1,1000000,min(a[pos],a[pos+1]),max(a[pos],a[pos+1]),-1);
				update(1,1,1000000,min(a[pos+1],val),max(a[pos+1],val),1);
			}
			a[pos]=val;
		}
		else{
			int h;
			cin >> h;
			cout << query(1,1,1000000,h,h) << '\n';
		}
	}
}

Compilation message

game.cpp: In function 'void update(int, int, int, int, int, int)':
game.cpp:22:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |  int m=l+r>>1;
      |        ~^~
game.cpp: In function 'int query(int, int, int, int, int)':
game.cpp:38:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |  int m=l+r>>1;
      |        ~^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 19 ms 19436 KB Output is correct
3 Correct 19 ms 18924 KB Output is correct
4 Correct 19 ms 19180 KB Output is correct
5 Correct 19 ms 19436 KB Output is correct
6 Correct 20 ms 19308 KB Output is correct
7 Correct 15 ms 15852 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 19 ms 19436 KB Output is correct
3 Correct 19 ms 18924 KB Output is correct
4 Correct 19 ms 19180 KB Output is correct
5 Correct 19 ms 19436 KB Output is correct
6 Correct 20 ms 19308 KB Output is correct
7 Correct 15 ms 15852 KB Output is correct
8 Correct 371 ms 1900 KB Output is correct
9 Correct 532 ms 27628 KB Output is correct
10 Correct 552 ms 27628 KB Output is correct
11 Correct 345 ms 1772 KB Output is correct
12 Correct 425 ms 3616 KB Output is correct
13 Correct 404 ms 27372 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 19 ms 19436 KB Output is correct
3 Correct 19 ms 18924 KB Output is correct
4 Correct 19 ms 19180 KB Output is correct
5 Correct 19 ms 19436 KB Output is correct
6 Correct 20 ms 19308 KB Output is correct
7 Correct 15 ms 15852 KB Output is correct
8 Correct 371 ms 1900 KB Output is correct
9 Correct 532 ms 27628 KB Output is correct
10 Correct 552 ms 27628 KB Output is correct
11 Correct 345 ms 1772 KB Output is correct
12 Correct 425 ms 3616 KB Output is correct
13 Correct 404 ms 27372 KB Output is correct
14 Correct 664 ms 27628 KB Output is correct
15 Correct 663 ms 27520 KB Output is correct
16 Correct 668 ms 27892 KB Output is correct
17 Correct 657 ms 27628 KB Output is correct
18 Correct 689 ms 27628 KB Output is correct