Submission #171065

#	Time	Username	Problem	Language	Result	Execution time	Memory
171065		mosiashvililuka	Simple game (IZhO17_game)	C++14	100 / 100	698 ms	13560 KiB

game

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,f[100009],tp,fen[200009],kk,zx,xc;
pair <int, int> p[100009];
map <int, int> m;
map <int, int>::iterator it;
void upd(int q, int w){
    while(q<=kk){
        fen[q]+=w;
        q=q+(q&(-q));
    }
}
int read(int q){
    int jm=0;
    while(q>=1){
        jm+=fen[q];
        q=q-(q&(-q));
    }
    return jm;
}
void mak(int q){
    if(q<1||q>=a) return;
    c=min(f[q],f[q+1]);
    d=max(f[q],f[q+1]);
    upd(c,-1);
    upd(d+1,1);
}
void makt(int q){
    if(q<1||q>=a) return;
    c=min(f[q],f[q+1]);
    d=max(f[q],f[q+1]);
    upd(c,1);
    upd(d+1,-1);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    //scanf("%d%d\n",&a,&b);
    for(i=1; i<=a; i++){
        cin>>f[i];
        //scanf("%d",&f[i]);
        m[f[i]]=1;
    }
    for(i=1; i<=b; i++){
        //scanf("%d",&tp);
        cin>>tp;
        if(tp==2){
            //scanf("%d\n",&c);
            cin>>c;
            p[i].first=c;
            m[p[i].first]=1;
        }else{
            //scanf("%d%d\n",&c,&d);
            cin>>c>>d;
            p[i].first=c;p[i].second=d;
            m[p[i].second]=1;
        }
    }
    c=0;
    for(it=m.begin(); it!=m.end(); it++){
        c++;
        m[(*it).first]=c;
    }
    for(i=1; i<=a; i++) f[i]=m[f[i]];
    for(i=1; i<=b; i++){
        if(p[i].second!=0) p[i].second=m[p[i].second]; else p[i].first=m[p[i].first];
    }
    /*for(i=1; i<=a+1; i++) cout<<f[i]<<" ";
    cout<<endl;
    for(i=1; i<=b; i++){
        cout<<p[i].first<<" "<<p[i].second<<endl;
    }*/
    kk=a+b+5;
    for(i=1; i<a; i++){
        c=min(f[i],f[i+1]);
        d=max(f[i],f[i+1]);
        upd(c,1);
        upd(d+1,-1);
    }
    for(i=1; i<=a; i++){
        if(p[i].second==0){
            cout<<read(p[i].first)<<endl;
        }else{
            mak(p[i].first);
            mak(p[i].first-1);
            f[p[i].first]=p[i].second;
            makt(p[i].first);
            makt(p[i].first-1);
        }
    }
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51