oj.uz

Submission #171065

# Submission time Handle Problem Language Result Execution time Memory
171065 2019-12-27T09:37:12 Z mosiashvililuka Simple game (IZhO17_game) C++14
100 / 100
 698 ms 13560 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 299 ms 2052 KB Output is correct
9 Correct 698 ms 13560 KB Output is correct
10 Correct 589 ms 13552 KB Output is correct
11 Correct 294 ms 2424 KB Output is correct
12 Correct 402 ms 5112 KB Output is correct
13 Correct 405 ms 8184 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 299 ms 2052 KB Output is correct
9 Correct 698 ms 13560 KB Output is correct
10 Correct 589 ms 13552 KB Output is correct
11 Correct 294 ms 2424 KB Output is correct
12 Correct 402 ms 5112 KB Output is correct
13 Correct 405 ms 8184 KB Output is correct
14 Correct 501 ms 12996 KB Output is correct
15 Correct 556 ms 13176 KB Output is correct
16 Correct 568 ms 13184 KB Output is correct
17 Correct 466 ms 13236 KB Output is correct
18 Correct 451 ms 13048 KB Output is correct