oj.uz

Submission #1118348

# Submission time Handle Problem Language Result Execution time Memory
1118348 2024-11-25T11:12:03 Z Younis_Dwai Simple game (IZhO17_game) C++14
100 / 100
 161 ms 13140 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
//#define int long long
#define in insert
#define mid (l+r)/2
#define in insert
using namespace std;
const int N=1e5+6;
int tree[N*40],b[N],n,m;
void upd(int node , int l , int r , int s,int e, int v){
     //cout<<" # "<<node<<' '<<l<<' '<<r<<endl;
     if(l>=s && r<=e){
        tree[node]+=v;
        return ;
     }
     else if(l>e || r<s) return ;
     upd(node*2,l,mid,s,e,v);
     upd(node*2+1,mid+1,r,s,e,v);
     return ;
}
int query(int node , int l , int r , int id){
    if(l>id || r<id) return 0;
    else if(l==r) return tree[node];
    return tree[node]+query(node*2,l,mid,id)+query(node*2+1,mid+1,r,id);
}
void modify(int id , int val){
     if(id+1<=n){
        upd(1,1,1e6,min(b[id],b[id+1]),max(b[id],b[id+1]),-1);
        upd(1,1,1e6,min(val,b[id+1]),max(val,b[id+1]),1);
     }
     if(id-1>=1){
        upd(1,1,1e6,min(b[id],b[id-1]),max(b[id],b[id-1]),-1);
        upd(1,1,1e6,min(val,b[id-1]),max(val,b[id-1]),1);
     }
     b[id]=val;
     return ;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<n;i++){
        int l=min(b[i],b[i+1]),r=max(b[i],b[i+1]);
        upd(1,1,1e6,l,r,1);
    }
    for(int i=1;i<=m;i++){
        int op;cin>>op;
        if(op==1){
           int pos,val;
           cin>>pos>>val;
           modify(pos,val);
        }
        else{
           int id;cin>>id;
           cout<<query(1,1,1e6,id)<<endl;
        }
    }
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 46 ms 7772 KB Output is correct
9 Correct 86 ms 12884 KB Output is correct
10 Correct 73 ms 13068 KB Output is correct
11 Correct 42 ms 7508 KB Output is correct
12 Correct 60 ms 8548 KB Output is correct
13 Correct 49 ms 4636 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 4 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 46 ms 7772 KB Output is correct
9 Correct 86 ms 12884 KB Output is correct
10 Correct 73 ms 13068 KB Output is correct
11 Correct 42 ms 7508 KB Output is correct
12 Correct 60 ms 8548 KB Output is correct
13 Correct 49 ms 4636 KB Output is correct
14 Correct 161 ms 12924 KB Output is correct
15 Correct 145 ms 13076 KB Output is correct
16 Correct 161 ms 12932 KB Output is correct
17 Correct 151 ms 13140 KB Output is correct
18 Correct 150 ms 13068 KB Output is correct