oj.uz

Submission #85768

# Submission time Handle Problem Language Result Execution time Memory
85768 2018-11-21T13:24:08 Z farukkastamonuda Simple game (IZhO17_game) C++14
100 / 100
 570 ms 35184 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define HOP 1000000
#define mid (start+end)/2
using namespace std;
int n,m,A[li],t,tree[HOP*4+5],lazy[HOP*4+5];
void push(int node,int start,int end){
	if(lazy[node]==0) return ;
	tree[node]+=lazy[node]*(end-start+1);
	if(start!=end){
		lazy[node*2]+=lazy[node];
		lazy[node*2+1]+=lazy[node];
	}
	lazy[node]=0;
}
void update(int node,int start,int end,int l,int r,int val){
	if(l>r) return ;
	push(node,start,end);
	if(start>end || start>r || end<l) return ;
	if(start>=l && end<=r){
		lazy[node]+=val;
		push(node,start,end);
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
int q1(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l) return 0;
	push(node,start,end);
	if(start>=l && end<=r) return tree[node];
	return q1(node*2,start,mid,l,r)+q1(node*2+1,mid+1,end,l,r);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
		if(i>1){
			int mn=min(A[i-1],A[i]);
			int mx=max(A[i-1],A[i]);
			update(1,1,HOP,mn+1,mx-1,1);
		}
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&t);
		if(t==2){
			int x;
			scanf("%d",&x);
			printf("%d\n",q1(1,1,HOP,x,x));
		}
		else{
			int pos,val;
			scanf("%d %d",&pos,&val);
			if(pos>1){
				int mn=min(A[pos-1],A[pos]);
				int mx=max(A[pos-1],A[pos]);
				update(1,1,HOP,mn+1,mx-1,-1);
			}
			if(pos<n){
				int mn=min(A[pos],A[pos+1]);
				int mx=max(A[pos],A[pos+1]);
				update(1,1,HOP,mn+1,mx-1,-1);
			}
			A[pos]=val;
			if(pos>1){
				int mn=min(A[pos-1],A[pos]);
				int mx=max(A[pos-1],A[pos]);
				update(1,1,HOP,mn+1,mx-1,1);
			}
			if(pos<n){
				int mn=min(A[pos],A[pos+1]);
				int mx=max(A[pos],A[pos+1]);
				update(1,1,HOP,mn+1,mx-1,1);
			}
		}
	}
	return 0;
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
game.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~
game.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
game.cpp:55:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&x);
    ~~~~~^~~~~~~~~
game.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d",&pos,&val);
    ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 20 ms 15072 KB Output is correct
3 Correct 19 ms 15212 KB Output is correct
4 Correct 17 ms 15352 KB Output is correct
5 Correct 18 ms 15352 KB Output is correct
6 Correct 22 ms 15352 KB Output is correct
7 Correct 14 ms 15352 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 20 ms 15072 KB Output is correct
3 Correct 19 ms 15212 KB Output is correct
4 Correct 17 ms 15352 KB Output is correct
5 Correct 18 ms 15352 KB Output is correct
6 Correct 22 ms 15352 KB Output is correct
7 Correct 14 ms 15352 KB Output is correct
8 Correct 110 ms 15352 KB Output is correct
9 Correct 287 ms 20492 KB Output is correct
10 Correct 272 ms 22124 KB Output is correct
11 Correct 72 ms 22124 KB Output is correct
12 Correct 159 ms 22124 KB Output is correct
13 Correct 224 ms 25848 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 20 ms 15072 KB Output is correct
3 Correct 19 ms 15212 KB Output is correct
4 Correct 17 ms 15352 KB Output is correct
5 Correct 18 ms 15352 KB Output is correct
6 Correct 22 ms 15352 KB Output is correct
7 Correct 14 ms 15352 KB Output is correct
8 Correct 110 ms 15352 KB Output is correct
9 Correct 287 ms 20492 KB Output is correct
10 Correct 272 ms 22124 KB Output is correct
11 Correct 72 ms 22124 KB Output is correct
12 Correct 159 ms 22124 KB Output is correct
13 Correct 224 ms 25848 KB Output is correct
14 Correct 495 ms 27560 KB Output is correct
15 Correct 570 ms 29424 KB Output is correct
16 Correct 542 ms 31300 KB Output is correct
17 Correct 520 ms 33372 KB Output is correct
18 Correct 481 ms 35184 KB Output is correct