Submission #1128767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128767		batyi	Simple game (IZhO17_game)	C++20	49 / 100	46 ms	25160 KiB

game

/*
|01|11|2010|
*/
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define sp setprecision
#define stl(v) v.begin(),v.end()
#define stlr(v) v.rbegin(),v.rend()
#define b1cnt __builtin_popcount

using namespace std;

const int N=1e6+12;
const int mod=1e9+7;
const int inf=1e18;
const int M=55;

int n,m;
int a[N];
int ans[N];
int cnt[N],cmt[N];

void prob(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n<=1000 && m<=1000){
		while(m--){
			int q;
			int x,y;
			cin>>q;
			if(q==1){
				cin>>x>>y;
				a[x]=y;
			}
			else{
				cin>>x;
				int ans=0;
				for(int i=2;i<=n;i++){
					if((a[i-1]>=x && a[i]<=x) || (a[i]>=x && a[i-1]<=x)) ans++;
				}
				cout<<ans<<"\n";
			}
		}
		return;
	}
	for(int i=1;i<=n-1;i++){
		int mn=min(a[i],a[i+1]);
		int mx=max(a[i],a[i+1]);
		cnt[mn+1]++;
		cmt[mx]--;
	}
	int cur=0;
	for(int i=1;i<=N;i++){
		cur+=cnt[i];
		ans[i]=cur;
		cur+=cmt[i];
	}
	while(m--){
		int t,h;
		cin>>t>>h;
		cout<<ans[h]<<"\n";
	}
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t2=1;
//    cin>>t2; 
    for(int test=1;test<=t2;test++){
        prob();
    }
}

//       ▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█|
//    ▄▄██▌█════Фура═с═Кодами════█|
// ▄▄▄▌▐██▌█═Приехала═Разгружаем═█|
// ███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█|
// ▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀(@)

Compilation message (stderr)

game.cpp: In function 'void prob()':
game.cpp:59:27: warning: iteration 1000011 invokes undefined behavior [-Waggressive-loop-optimizations]
   59 |                 cur+=cnt[i];
      |                      ~~~~~^
game.cpp:58:22: note: within this loop
   58 |         for(int i=1;i<=N;i++){
      |                     ~^~~

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