oj.uz

답안 #101483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101483 2019-03-19T03:07:50 Z errorgorn 케이크 (CEOI14_cake) C++14
66.6667 / 100
 2000 ms 5568 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <deque>
using namespace std;
typedef pair<int,int> ii;
int n,d,q;
int E,F;
int arr[250005],top[12];
int memo[250005];
ii query[500005];
int f(int i){
    if (d==i) return 0;
    else{
        int ans=1;
        ii a=ii(1000000000,-1), b=ii(1000000000,-1);
        if (d!=0) a=ii(arr[d-1],d-1);
        if (d!=n-1) b=ii(arr[d+1],d+1);
        if (a>b) swap(a,b);
        while (a.second!=i){
            //printf("%d %d\n",a.second,b.second);
            if (a.second<d){
                if (a.second!=0) a=ii(arr[a.second-1],a.second-1);
                else a=ii(1000000000,-1);
            }
            else{
                if (a.second!=n-1) a=ii(arr[a.second+1],a.second+1);
                else a=ii(1000000000,-1);
            }
            if (a>b) swap(a,b);
            ans++;
        }
        return ans;
    }
}
void memof(){
    memo[d]=0;
    int ans=1;
    ii a=ii(1000000000,-1), b=ii(1000000000,-1);
    if (d!=0) a=ii(arr[d-1],d-1);
    if (d!=n-1) b=ii(arr[d+1],d+1);
    if (a>b) swap(a,b);
    while (a.first!=1000000000){
        memo[a.second]=ans++;
        if (a.second<d){
            if (a.second!=0) a=ii(arr[a.second-1],a.second-1);
            else a=ii(1000000000,-1);
        }
        else{
            if (a.second!=n-1) a=ii(arr[a.second+1],a.second+1);
            else a=ii(1000000000,-1);
        }
        if (a>b) swap(a,b);
    }
}
void print(){
    for (int x=0;x<n;x++){
        printf("%d ",memo[x]);
    }
    printf("\n\n");
}
int main(){
    //freopen("input.txt","r",stdin);
    int a,b;
    scanf("%d%d",&n,&d);
    d--;
    for (int x=0;x<n;x++){
        scanf("%d",&arr[x]);
    }
    scanf("%d",&q);
    for (int x=0;x<q;x++){
        getchar();
        if (getchar()=='E'){
            scanf("%d%d",&a,&b);
            query[x]=(ii(a-1,b-1));
            E++;
        }
        else{
            scanf("%d",&a);
            query[x]=(ii(a-1,-1));
            F++;
        }
    }
    for (int x=0;x<n;x++){
        if (arr[x]>n-10) top[n-arr[x]]=x;
    }
    int tb=min(n,10);
    ii it;
    if (E<=100){
        memof();
        for (int __x=0;__x<q;__x++){
            it=query[__x];
            if ((it).second==-1){ //this is F
                printf("%d\n",memo[(it).first]);
            }
            else{ //this is E
                arr[(it).first]=arr[top[(it).second]]+1;
                for (int x=0;x<(it).second;x++){
                    arr[top[x]]++;
                }
                int _x;
                for (_x=(it).second;_x<tb && top[_x]!=(it).first;_x++){}
                for (int x=_x;x>(it).second;x--){
                    top[x]=top[x-1];
                }
                top[(it).second]=(it).first;
                memof();
                //print();
            }
        }
    }
    else {
        for (int __x=0;__x<q;__x++){
            it=query[__x];
            if ((it).second==-1){ //this is F
                printf("%d\n",f((it).first));
            }
            else{ //this is E
                arr[(it).first]=arr[top[(it).second]]+1;
                for (int x=0;x<(it).second;x++){
                    arr[top[x]]++;
                }
                int _x;
                for (_x=(it).second;_x<tb && top[_x]!=(it).first;_x++){}
                for (int x=_x;x>(it).second;x--){
                    top[x]=top[x-1];
                }
                top[(it).second]=(it).first;
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&d);
     ~~~~~^~~~~~~~~~~~~~
cake.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
cake.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 68 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 4324 KB Output is correct
2 Correct 124 ms 4316 KB Output is correct
3 Correct 129 ms 4316 KB Output is correct
4 Correct 91 ms 4188 KB Output is correct
5 Correct 110 ms 4344 KB Output is correct
6 Correct 105 ms 4344 KB Output is correct
7 Correct 108 ms 4344 KB Output is correct
8 Correct 107 ms 4344 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 2476 KB Output is correct
2 Correct 54 ms 2396 KB Output is correct
3 Correct 64 ms 2296 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 92 ms 3676 KB Output is correct
6 Correct 101 ms 3704 KB Output is correct
7 Correct 81 ms 3480 KB Output is correct

Subtask #4
16.666667 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 880 KB Output is correct
2 Correct 118 ms 988 KB Output is correct
3 Correct 1484 ms 1596 KB Output is correct
4 Correct 1577 ms 1532 KB Output is correct
5 Correct 170 ms 1784 KB Output is correct
6 Execution timed out 2041 ms 2156 KB Time limit exceeded
7 Correct 837 ms 2576 KB Output is correct
8 Correct 185 ms 2448 KB Output is correct
9 Execution timed out 2019 ms 5568 KB Time limit exceeded
10 Correct 585 ms 5496 KB Output is correct
11 Execution timed out 2049 ms 5112 KB Time limit exceeded
12 Execution timed out 2062 ms 5412 KB Time limit exceeded
13 Execution timed out 2053 ms 5496 KB Time limit exceeded