Submission #672981

#	Time	Username	Problem	Language	Result	Execution time	Memory
672981		ReLice	Simple game (IZhO17_game)	C++14	100 / 100	418 ms	64872 KiB

game

#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 (stderr)

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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51