oj.uz

Submission #486349

# Submission time Handle Problem Language Result Execution time Memory
486349 2021-11-11T10:55:29 Z Sho10 Simple game (IZhO17_game) C++17
100 / 100
 80 ms 11116 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 998244353
#define PI 3.14159265359
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,m,h[100005],bit[1000005],mxx=1000000;
void upd(ll pos,ll val){
for(;pos<=mxx;pos+=pos&(-pos)){
    bit[pos]+=val;
}
}
void update(ll x,ll y,ll val){
if(x>y){
    swap(x,y);
}
upd(x,val);
upd(y+1,-val);
}
ll query(ll pos){
ll res=0;
for(;pos;pos-=pos&(-pos)){
    res+=bit[pos];
}
return res;
}
int32_t main(){
CODE_START;
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
    cin>>h[i];
    if(i>=2){
        update(h[i],h[i-1],1ll);
    }
}
while(m--){
    ll type;
    cin>>type;
    if(type==2){
        ll pos;
        cin>>pos;
        cout<<query(pos)<<endl;
    }else if(type==1){
    ll pos,val;
    cin>>pos>>val;
    ll i=pos;
    if(pos>=2){
update(h[i],h[i-1],-1);
    }
    if(pos<n){
        update(h[i],h[i+1],-1);
    }
    h[i]=val;
    if(pos>=2){
        update(h[i],h[i-1],1);
    }
    if(pos<n){
        update(h[i],h[i+1],1);
    }
}
}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 4 ms 6732 KB Output is correct
3 Correct 3 ms 6604 KB Output is correct
4 Correct 4 ms 6732 KB Output is correct
5 Correct 3 ms 6604 KB Output is correct
6 Correct 4 ms 6860 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 4 ms 6732 KB Output is correct
3 Correct 3 ms 6604 KB Output is correct
4 Correct 4 ms 6732 KB Output is correct
5 Correct 3 ms 6604 KB Output is correct
6 Correct 4 ms 6860 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 33 ms 2108 KB Output is correct
9 Correct 45 ms 11084 KB Output is correct
10 Correct 45 ms 11096 KB Output is correct
11 Correct 29 ms 1972 KB Output is correct
12 Correct 33 ms 3284 KB Output is correct
13 Correct 36 ms 3156 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 4 ms 6732 KB Output is correct
3 Correct 3 ms 6604 KB Output is correct
4 Correct 4 ms 6732 KB Output is correct
5 Correct 3 ms 6604 KB Output is correct
6 Correct 4 ms 6860 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 33 ms 2108 KB Output is correct
9 Correct 45 ms 11084 KB Output is correct
10 Correct 45 ms 11096 KB Output is correct
11 Correct 29 ms 1972 KB Output is correct
12 Correct 33 ms 3284 KB Output is correct
13 Correct 36 ms 3156 KB Output is correct
14 Correct 68 ms 11072 KB Output is correct
15 Correct 69 ms 11028 KB Output is correct
16 Correct 64 ms 11116 KB Output is correct
17 Correct 69 ms 11076 KB Output is correct
18 Correct 80 ms 11112 KB Output is correct