oj.uz

Submission #334920

# Submission time Handle Problem Language Result Execution time Memory
334920 2020-12-10T09:06:00 Z zaneyu Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 10580 KB 
/*input
5 3
5 1 2 4 3
17
F 1
F 2
F 3
F 4
F 5
E 2 1
F 1
F 2
F 3
F 4
F 5
E 5 2
F 1
F 2
F 3
F 4
F 5
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll sub(ll a,ll b){
    ll x=a-b;
    while(x<0) x+=MOD;
    while(x>MOD) x-=MOD;
    return x;
}
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
const int maxn=6e5+5;
const ll maxlg=__lg(maxn)+2;
struct segt{
    int seg[4*maxn];
    int n;
    void resize(int _n){
        n=_n;
    } 
    void mdf(int idx,int l,int r,int p,int x){
        if(r<p or l>p) return;
        if(l==r){
            seg[idx]=x;
            return;
        }
        int mid=(l+r)/2;
        mdf(idx*2,l,mid,p,x);
        mdf(idx*2+1,mid+1,r,p,x);
        seg[idx]=max(seg[idx*2],seg[idx*2+1]);
    }
    ll query(int idx,int l,int r,int ql,int qr){
        if(l>qr or r<ql) return 0;
        if(ql<=l and r<=qr) return seg[idx];
        int mid=(l+r)/2;
        return max(query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr));
    }
    ll query(int l,int r){
        if(l>r) return 0;
        return query(1,0,n-1,l,r);
    }
    void mdf(int p,int x){
        mdf(1,0,n-1,p,x);
    }
}arr;
int pos[maxn];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,a;
    cin>>n>>a;
    arr.resize(n+2);
    arr.mdf(0,INF),arr.mdf(n+1,INF);
    REP1(i,n){
        int x;
        cin>>x;
        arr.mdf(i,x);
        if(n-x<=10) pos[n-x]=i;
    }
    int q;
    cin>>q;
    while(q--){
        char x;
        int p;
        cin>>x>>p;
        if(x=='F'){
            if(p==a){
                cout<<"0\n";
            }
            else if(p<a){
                int l=a,r=n+1;
                while(l<r){
                    int mid=(l+r+1)/2;
                    if(arr.query(a+1,mid)>arr.query(p,a-1)) r=mid-1;
                    else l=mid;
                }
                cout<<(l-p)<<'\n';
            }
            else{
                int l=0,r=a;
                while(l<r){
                    int mid=(l+r)/2;
                    if(arr.query(mid,a-1)>arr.query(a+1,p)) l=mid+1;
                    else r=mid;
                }
                cout<<(p-l)<<'\n';
            }
        }
        else{
            int y;
            cin>>y;
            int ps=10;
            REP(i,10){
                if(pos[i]==p) ps=i;
            }
            arr.mdf(p,arr.query(pos[y-1],pos[y-1])+1);
            while(ps>=y){
                pos[ps]=pos[ps-1];
                ps--;
            }
            pos[y-1]=p;
            REP(i,y-1) arr.mdf(pos[i],arr.query(pos[i],pos[i])+1);
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 8 ms 364 KB Output is correct
5 Correct 27 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 5100 KB Output is correct
2 Correct 259 ms 4888 KB Output is correct
3 Correct 301 ms 5100 KB Output is correct
4 Correct 179 ms 4972 KB Output is correct
5 Correct 472 ms 5356 KB Output is correct
6 Correct 387 ms 5612 KB Output is correct
7 Correct 319 ms 5740 KB Output is correct
8 Correct 189 ms 5740 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 3376 KB Output is correct
2 Correct 382 ms 3180 KB Output is correct
3 Correct 353 ms 3180 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 649 ms 5572 KB Output is correct
6 Correct 757 ms 5508 KB Output is correct
7 Correct 529 ms 5484 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 992 KB Output is correct
2 Correct 111 ms 1004 KB Output is correct
3 Correct 267 ms 2028 KB Output is correct
4 Correct 247 ms 2028 KB Output is correct
5 Correct 253 ms 2028 KB Output is correct
6 Correct 534 ms 3052 KB Output is correct
7 Correct 399 ms 2540 KB Output is correct
8 Correct 187 ms 3948 KB Output is correct
9 Execution timed out 2087 ms 10580 KB Time limit exceeded
10 Correct 846 ms 5276 KB Output is correct
11 Correct 1320 ms 6236 KB Output is correct
12 Execution timed out 2019 ms 10360 KB Time limit exceeded
13 Execution timed out 2080 ms 10532 KB Time limit exceeded