oj.uz

Submission #25929

# Submission time Handle Problem Language Result Execution time Memory
25929 2017-06-25T06:37:58 Z 시제연(#1089) Cake (CEOI14_cake) C++
35 / 100
 416 ms 11460 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> lst, rst;
int value[250100];
int ord[750100];
int pre[750100];
int n, q, a, maxv;
int arr[250100];

int getbef(int idx) {
    if (pre[idx]==-1||~ord[pre[idx]]) return pre[idx];
    return pre[idx] = (getbef(pre[idx]));
}

vector<int> comp;
void com(int arr[], int val[]) {
    int i;
    for (i=0;i<n;i++) comp.push_back(arr[i]);
    sort(comp.begin(),comp.end());
    for (i=0;i<n;i++) val[i] = lower_bound(comp.begin(),comp.end(),arr[i])-comp.begin();
}

void push(vector<int> &st, int val) {
    if (st.empty()||value[st.back()]<value[val]) st.push_back(val);
}

void deb() {
    int i;

    for (i=0;i<lst.size();i++) {
        printf("%d : %d, ",lst[i],value[lst[i]]);
    }
    printf("\n");

    for (i=0;i<rst.size();i++) {
        printf("%d : %d, ",rst[i],value[rst[i]]);
    }
    printf("\n\n");

    /*
    for (i=0;i<n;i++) printf("%d ",value[i]);
    printf("\n");
    for (i=0;i<=maxv;i++) printf("%d ",ord[i]);
    printf("\n");
    */
}

stack<int> tt;
void stupd(vector<int> &st, int idx, int sg) {
    while(!st.empty()&&st.back()*sg>=idx*sg) {
        tt.push(st.back());
        st.pop_back();
    }
    if (tt.empty()||tt.top()!=idx) tt.push(idx);
    while(!tt.empty()) {
        push(st,tt.top());
        tt.pop();
    }
}

vector<int> can;
void upd(int idx, int e) {
    if (idx==a) return;
    can.clear();
    int i, p = maxv;
    for (i=0;i<e-1;i++) {
        can.push_back(p);
        p = getbef(p);
    }
    can.push_back(value[idx]);
    int q = value[idx];
    maxv++;
    for (i=0;i<can.size();i++) {
        value[ord[can[i]]] = ((i)?can[i-1]:maxv);
        ord[((i)?can[i-1]:maxv)] = ord[can[i]];
    }
    ord[q] = -1;

    if (idx<a) stupd(lst,idx,-1);
    else if (idx>a) stupd(rst,idx,1);
}

int ibs(vector<int> &st, int idx, int sg) {
    int s = 0, e = (int)st.size()-1;
    while(s<=e) {
        int m = (s+e)>>1;
        if (sg*st[m]<=sg*idx) s = m+1;
        else e = m-1;
    }
    return e;
}

int vbs(vector<int> &st, int val) {
    int s = 0, e = (int)st.size()-1;
    while(s<=e) {
        int m = (s+e)>>1;
        if (value[st[m]]<val) s = m+1;
        else e = m-1;
    }
    return s;
}

int query(int b) {
    if (b==a) return 0;
    if (b>a) {
        int idx =vbs(lst,value[rst[ibs(rst,b,1)]]);
        return b-((idx==lst.size())?-1:lst[idx])-1;
    }
    int idx = vbs(rst,value[lst[ibs(lst,b,-1)]]);
    return ((idx==rst.size())?n:rst[idx])-b-1;
}

int main() {
    int i;

    //freopen("input","r",stdin);

    scanf("%d%d",&n,&a);
    a--;
    for (i=0;i<n;i++) scanf("%d",&arr[i]);
    com(arr,value);
    maxv = n-1;
    for (i=0;i<n;i++) ord[value[i]] = i;
    for (i=a-1;i>=0;i--) push(lst,i);
    for (i=a+1;i<n;i++) push(rst,i);
    scanf("%d",&q);
    for (i=0;i<n+q;i++) pre[i] = i-1;
    for (i=0;i<q;i++) {
        char que[3];
        scanf("%s",que);
        if (que[0]=='E') {
            int a, b;
            scanf("%d%d",&a,&b);
            upd(--a,b);
        }
        else {
            int b;
            scanf("%d",&b);
            printf("%d\n",query(--b));
        }
    }

    return 0;
}

Compilation message

cake.cpp: In function 'void deb()':
cake.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lst.size();i++) {
               ^
cake.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<rst.size();i++) {
               ^
cake.cpp: In function 'void upd(int, int)':
cake.cpp:75:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<can.size();i++) {
               ^
cake.cpp: In function 'int query(int)':
cake.cpp:109:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         return b-((idx==lst.size())?-1:lst[idx])-1;
                       ^
cake.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return ((idx==rst.size())?n:rst[idx])-b-1;
                 ^
cake.cpp: In function 'int main()':
cake.cpp:120:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&a);
                        ^
cake.cpp:122:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%d",&arr[i]);
                                          ^
cake.cpp:128:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
cake.cpp:132:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",que);
                        ^
cake.cpp:135:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
                                ^
cake.cpp:140:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
                           ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9840 KB Output is correct
2 Correct 0 ms 9840 KB Output is correct
3 Correct 0 ms 9840 KB Output is correct
4 Incorrect 3 ms 9840 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9980 KB Output is correct
2 Correct 209 ms 9980 KB Output is correct
3 Correct 196 ms 9980 KB Output is correct
4 Correct 146 ms 9980 KB Output is correct
5 Correct 243 ms 10112 KB Output is correct
6 Correct 236 ms 10112 KB Output is correct
7 Correct 226 ms 10112 KB Output is correct
8 Correct 173 ms 10112 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 10692 KB Output is correct
2 Correct 76 ms 10692 KB Output is correct
3 Correct 66 ms 10692 KB Output is correct
4 Correct 0 ms 9840 KB Output is correct
5 Correct 173 ms 11460 KB Output is correct
6 Correct 159 ms 11460 KB Output is correct
7 Correct 123 ms 11460 KB Output is correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 9840 KB Output isn't correct
2 Incorrect 26 ms 9980 KB Output isn't correct
3 Incorrect 59 ms 10308 KB Output isn't correct
4 Correct 59 ms 10308 KB Output is correct
5 Incorrect 59 ms 9840 KB Output isn't correct
6 Correct 109 ms 10692 KB Output is correct
7 Correct 89 ms 9980 KB Output is correct
8 Correct 103 ms 10692 KB Output is correct
9 Correct 416 ms 11460 KB Output is correct
10 Incorrect 199 ms 9840 KB Output isn't correct
11 Correct 236 ms 10112 KB Output is correct
12 Correct 413 ms 11460 KB Output is correct
13 Correct 316 ms 11460 KB Output is correct