oj.uz

Submission #672981

# Submission time Handle Problem Language Result Execution time Memory
672981 2022-12-19T09:35:55 Z ReLice Simple game (IZhO17_game) C++14
100 / 100
 418 ms 64872 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long
#define ld long double
#define int long long
#define pb push_back
#define sz size()
#define fr first
#define sc second
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
void fre(string n){freopen((n+".in").c_str(),"r",stdin);freopen((n+".out").c_str(),"w",stdin);}
const ll N = 1e6 + 10 ;
const ll inf=1e9+7;
vector <ll> t(4*N),add(4*N);
ll n;
void push(ll v,ll tl,ll tr){
    if(tl==tr)t[v]+=add[v];
    else{
        add[v*2]+=add[v];
        add[v*2+1]+=add[v];
    }
    add[v]=0;
}
void update(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(tl>r || tr<l) return;
    if(l<=tl && tr<=r){
        add[v]++;
        push(v,tl,tr);
        return;
    }
    ll tm=(tl+tr)/2;
    update(v*2,tl,tm,l,r);
    update(v*2+1,tm+1,tr,l,r);
}
void update2(ll v,ll tl,ll tr, ll l,ll r){
    push(v,tl,tr);
    if(tl>r || tr<l) return;
    if(l<=tl && tr<=r){
        add[v]--;
        push(v,tl,tr);
        return;
    }
    ll tm=(tl+tr)/2;
    update2(v*2,tl,tm,l,r);
    update2(v*2+1,tm+1,tr,l,r);
}
ll get(ll v,ll tl,ll tr, ll pos){
    push(v,tl,tr);
    if(tl>pos || tr<pos) return 0;
    if(tl==tr){
        push(v,tl,tr);
        return t[v];
    }
    ll tm=(tl+tr)/2;
    return get(v*2,tl,tm,pos)+get(v*2+1,tm+1,tr,pos);
}
void solve(){
    ll i,b,q;
    cin>>n>>q;
    vector <ll> v;
    v.pb(0);
    for(i=1;i<=n;i++){
        cin>>b;
        v.pb(b);
        if(i>1) update(1,1,1000000,min(v[i-1],v[i]),max(v[i-1],v[i]));
    }
    while(q--){
        ll tp; cin>>tp;
        if(tp==1){
            ll id,h;
            cin>>id>>h;
            if(id>1){
                update2(1,1,1000000,min(v[id-1],v[id]),max(v[id-1],v[id]));
                update(1,1,1000000,min(v[id-1],h),max(v[id-1],h));
            }
            if(id<n){
                update2(1,1,1000000,min(v[id+1],v[id]),max(v[id+1],v[id]));
                update(1,1,1000000,min(v[id+1],h),max(v[id+1],h));
            }
            v[id]=h;
        }
        else {
            ll pos;
            cin>>pos;
            cout<<get(1,1,1000000,pos)<<endl;
        }
    }
}
main(){
    //fre("");
    //start();
    ll t=1;
    //cin>>t;
    while(t--)solve();

}
/*
3 3
1 5 1
2 3
1 1 5
2 3
*/

Compilation message

game.cpp:95:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   95 | main(){
      | ^~~~
game.cpp: In function 'void fre(std::string)':
game.cpp:16:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | void fre(string n){freopen((n+".in").c_str(),"r",stdin);freopen((n+".out").c_str(),"w",stdin);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:16:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 | void fre(string n){freopen((n+".in").c_str(),"r",stdin);freopen((n+".out").c_str(),"w",stdin);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 26 ms 62880 KB Output is correct
3 Correct 27 ms 62924 KB Output is correct
4 Correct 27 ms 62960 KB Output is correct
5 Correct 26 ms 62956 KB Output is correct
6 Correct 30 ms 62944 KB Output is correct
7 Correct 30 ms 62952 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 26 ms 62880 KB Output is correct
3 Correct 27 ms 62924 KB Output is correct
4 Correct 27 ms 62960 KB Output is correct
5 Correct 26 ms 62956 KB Output is correct
6 Correct 30 ms 62944 KB Output is correct
7 Correct 30 ms 62952 KB Output is correct
8 Correct 246 ms 64352 KB Output is correct
9 Correct 341 ms 64624 KB Output is correct
10 Correct 334 ms 64872 KB Output is correct
11 Correct 235 ms 64308 KB Output is correct
12 Correct 289 ms 64716 KB Output is correct
13 Correct 275 ms 64728 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 62932 KB Output is correct
2 Correct 26 ms 62880 KB Output is correct
3 Correct 27 ms 62924 KB Output is correct
4 Correct 27 ms 62960 KB Output is correct
5 Correct 26 ms 62956 KB Output is correct
6 Correct 30 ms 62944 KB Output is correct
7 Correct 30 ms 62952 KB Output is correct
8 Correct 246 ms 64352 KB Output is correct
9 Correct 341 ms 64624 KB Output is correct
10 Correct 334 ms 64872 KB Output is correct
11 Correct 235 ms 64308 KB Output is correct
12 Correct 289 ms 64716 KB Output is correct
13 Correct 275 ms 64728 KB Output is correct
14 Correct 409 ms 64416 KB Output is correct
15 Correct 418 ms 64476 KB Output is correct
16 Correct 413 ms 64360 KB Output is correct
17 Correct 406 ms 64460 KB Output is correct
18 Correct 416 ms 64380 KB Output is correct