oj.uz

Submission #101473

# Submission time Handle Problem Language Result Execution time Memory
101473 2019-03-19T02:56:10 Z errorgorn Cake (CEOI14_cake) C++14
46.6667 / 100
 2000 ms 5484 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];
ii query[500005];
void print(){
    for (int x=0;x<n;x++){
        printf("%d ",arr[x]);
    }
    printf("\n");
    for (int x=0;x<min(n,10);x++){
        printf("%d ",top[x]);
    }
    printf("\n");
}
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 print2(){
    for (int x=0;x<n;x++){
        printf("%d ",f(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;
    //print();
    if ( (n<=10000 && q<=10000) || F<=500 ||true){
        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;
                //print();
                //print2();
            }
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:54: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:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~
cake.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
cake.cpp:63: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:68: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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 62 ms 504 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 4300 KB Output is correct
2 Correct 128 ms 4160 KB Output is correct
3 Correct 106 ms 4216 KB Output is correct
4 Correct 157 ms 4316 KB Output is correct
5 Correct 131 ms 4316 KB Output is correct
6 Correct 130 ms 4420 KB Output is correct
7 Correct 142 ms 4316 KB Output is correct
8 Correct 144 ms 4348 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2003 ms 1820 KB Time limit exceeded
2 Execution timed out 2050 ms 1912 KB Time limit exceeded
3 Execution timed out 2036 ms 1920 KB Time limit exceeded
4 Correct 2 ms 384 KB Output is correct
5 Execution timed out 2057 ms 2304 KB Time limit exceeded
6 Execution timed out 2036 ms 2168 KB Time limit exceeded
7 Execution timed out 2056 ms 2440 KB Time limit exceeded

Subtask #4
16.666667 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 888 KB Output is correct
2 Correct 108 ms 860 KB Output is correct
3 Correct 1452 ms 1396 KB Output is correct
4 Correct 1479 ms 1452 KB Output is correct
5 Correct 166 ms 1912 KB Output is correct
6 Execution timed out 2052 ms 2168 KB Time limit exceeded
7 Correct 816 ms 2552 KB Output is correct
8 Correct 188 ms 2296 KB Output is correct
9 Execution timed out 2044 ms 5388 KB Time limit exceeded
10 Correct 506 ms 5484 KB Output is correct
11 Execution timed out 2050 ms 5064 KB Time limit exceeded
12 Execution timed out 2033 ms 5392 KB Time limit exceeded
13 Execution timed out 2058 ms 5372 KB Time limit exceeded