Submission #1128795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128795		satbergen	Simple game (IZhO17_game)	C++20	49 / 100	47 ms	25156 KiB

game

#include <bits/stdc++.h>
    #define y1 sat
    #define dl double
    #define int long long
    #define ff first
    #define ss second
    // #define sz size
    #define pb push_back
    #define wrans cout << -1
    #define neutral cout << 0  
using namespace std;
const int N=1e6+100;
const int M=2600;
const int MOD=1e9+7;  
const double long E=2.718281828459045;
const double long pi=3.14159265359;
const long long INF=1e18;
int a[N];
int cnt[N];
int cnt1[N];
int ans[N];
// ╔╗╔╗╔╗╔╗╔╗╔╗╔═╗
// ║║║║║║║║║║║║╚╗║
// ║╚╝║║║║║║╚╝║╔╝║
// ║╔╗║║║║║║╔╗║║╔╝11
// ║║║║║╚╝║║║║║╔╗─
// ╚╝╚╝╚══╝╚╝╚╝╚╝─
// int binpow(int a,int b){
//     if(b==0) return 1;    
//     if(b%2 == 0){
//         int x=binpow(a,b/2);
//         return (x*x)%MOD;
//     }
//     else  return (a*binpow(a,b-1))%MOD;
// }
void solve(){
    int n,m;
    cin >> n >> m;
    map <int,int> mp;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    if(n<=1000 && m<=1000){
        for(int i = 1 ; i <= m ; i++){
            int q;
            cin >> q;
            if(q==1){
                int v,h;
                cin >> v >> h;
                a[v]=h;
            }
            else{
                int h;
                cin >> h;
                int cnt=0;
                for(int i=1;i<n;i++){
                    if(min(a[i],a[i+1])<h && max(a[i],a[i+1])>h){
                        cnt++;
                    }
                }
                cout<<cnt<<"\n";
            }
        }
        return;
    }
    for(int i=1;i<n;i++){
        int mn=min(a[i],a[i+1]);
        int mx=max(a[i],a[i+1]);
        cnt[mn]++;
        cnt1[mx]--;
    }
    int res=0;
    for(int i=1;i<=N;i++){
        res+=cnt[i];
        ans[i]=res;
        res+=cnt1[i];
    }
    for(int t,x;m--;){
        cin>>t>>x;
        cout<<ans[x]<<'\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//  cout.tie(0);
    // for(int i = 2 ; i <= INF ; i++){
    //     if(prime[i]==0){
    //         for(int j = 2 ; i*j<=INF ; j++){
    //             prime[i*j]=1;
    //         }
    //     }
    // }
    // fact();
    int test=1;
    // cin >> test;   
    while(test--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

game.cpp: In function 'void solve()':
game.cpp:74:19: warning: iteration 1000099 invokes undefined behavior [-Waggressive-loop-optimizations]
   74 |         res+=cnt[i];
      |              ~~~~~^
game.cpp:73:18: note: within this loop
   73 |     for(int i=1;i<=N;i++){
      |                 ~^~~

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