oj.uz

Submission #758213

# Submission time Handle Problem Language Result Execution time Memory
758213 2023-06-14T09:33:10 Z vjudge1 Simple game (IZhO17_game) C++14
100 / 100
 177 ms 18928 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;
int N,L,R,V;
int seg[6000000];
void slv(int l=1,int r=N,int in=1){
    if(l>R||r<L)return;
    if(l>=L&&r<=R){
        seg[in]+=V;
        return;
    }
    int mid=(l+r)/2;
    slv(l,mid,in*2);slv(mid+1,r,in*2+1);
}
void add(int l,int r,int v){
    if(l>r)swap(l,r);
    if(r==l+1)return;
    L=l,R=r,V=v;
    slv();
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    N=exp2(ceil(log2(1000000)));
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
        if(i)add(arr[i],arr[i-1],1);
    }
    while(m--){
        int t;
        cin>>t;
        if(t&1){
            int in,x;
            cin>>in>>x;
            in--;
            if(in)add(arr[in],arr[in-1],-1);
            if(in<n-1)add(arr[in],arr[in+1],-1);
            arr[in]=x;
            if(in)add(arr[in],arr[in-1],1);
            if(in<n-1)add(arr[in],arr[in+1],1);
        }else{
            int h,ans=0;
            cin>>h;
            h+=N-1;
            while(h){
                ans+=seg[h];
                h/=2;
            }
            cout<<ans<<endl;
        }
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 9556 KB Output is correct
3 Correct 6 ms 9172 KB Output is correct
4 Correct 6 ms 9300 KB Output is correct
5 Correct 6 ms 9300 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 2 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 9556 KB Output is correct
3 Correct 6 ms 9172 KB Output is correct
4 Correct 6 ms 9300 KB Output is correct
5 Correct 6 ms 9300 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 40 ms 1252 KB Output is correct
9 Correct 92 ms 17356 KB Output is correct
10 Correct 93 ms 17276 KB Output is correct
11 Correct 29 ms 1256 KB Output is correct
12 Correct 55 ms 2140 KB Output is correct
13 Correct 41 ms 1656 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 9556 KB Output is correct
3 Correct 6 ms 9172 KB Output is correct
4 Correct 6 ms 9300 KB Output is correct
5 Correct 6 ms 9300 KB Output is correct
6 Correct 6 ms 9428 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 40 ms 1252 KB Output is correct
9 Correct 92 ms 17356 KB Output is correct
10 Correct 93 ms 17276 KB Output is correct
11 Correct 29 ms 1256 KB Output is correct
12 Correct 55 ms 2140 KB Output is correct
13 Correct 41 ms 1656 KB Output is correct
14 Correct 162 ms 17056 KB Output is correct
15 Correct 177 ms 18892 KB Output is correct
16 Correct 175 ms 18892 KB Output is correct
17 Correct 176 ms 18912 KB Output is correct
18 Correct 167 ms 18928 KB Output is correct