Submission #890438

#	Time	Username	Problem	Language	Result	Execution time	Memory
890438		alex_2008	Simple game (IZhO17_game)	C++14	49 / 100	185 ms	7096 KiB

game

#include <bits/stdc++.h>
using namespace std;
 
const int N=1e5+5, M=1e6+10;
int a[N], b[M];
int n,m;
 
void precalc(){
	for(int i=0; i<n-1; i++){
		b[min(a[i], a[i+1])]++;
      	b[max(a[i], a[i+1])+1]--;		
	}
  	for(int i=1;i<M;i++){
      b[i]+=b[i-1];
	}
}
 
int main() {
	cin>>n>>m;
	int mx=-1;
	for(int i=0; i<n; i++){cin>>a[i]; mx=max(mx, a[i]);}
	if(n <= 1000 && m<=1000){
		for(int i=0; i<m; i++){
			int q;
			cin>>q;
			if(q==2){
				long long anss=0;
				int h;
				cin>>h;
				for(int i=0; i<n-1; i++){
					if(a[i] >= h && a[i+1] <= h)anss++;
					else if(a[i] <= h && a[i+1] >= h)anss++;
				}
				cout<<anss<<endl;
			}else{
				int c,d;
				cin>>c>>d;
				a[c-1] = d;
			}
		}
		return 0;
	}
	precalc();
//	for(int i=1; i<=mx; i++)cout<<b[i]<<" ";
//	cout<<endl;
	for(int i=0; i<m; i++){
		int q;
		cin>>q;
		if(q==2){
			int h;
			cin>>h;
			cout<<b[h]<<"\n";
		}else{
			int a,b;
			cin>>a>>b;
		}
	}
	
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 0 / 51