답안 #25931 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25931	2017-06-25T06:41:12 Z	시제연(#1089)	케이크 (CEOI14_cake)	C++	100 / 100	406 ms	11460 KB

cake

#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) {
    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:74: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:108:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         return b-((idx==lst.size())?-1:lst[idx])-1;
                       ^
cake.cpp:111: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:119: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:121: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:127:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
                   ^
cake.cpp:131:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",que);
                        ^
cake.cpp:134: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:139:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&b);
                           ^

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	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	Correct	3 ms	9840 KB	Output is correct
5	Correct	6 ms	9980 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	203 ms	9980 KB	Output is correct
2	Correct	183 ms	9980 KB	Output is correct
3	Correct	189 ms	9980 KB	Output is correct
4	Correct	146 ms	9980 KB	Output is correct
5	Correct	279 ms	10112 KB	Output is correct
6	Correct	253 ms	10112 KB	Output is correct
7	Correct	243 ms	10112 KB	Output is correct
8	Correct	186 ms	10112 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	76 ms	10692 KB	Output is correct
2	Correct	63 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	163 ms	11460 KB	Output is correct
6	Correct	169 ms	11460 KB	Output is correct
7	Correct	119 ms	11460 KB	Output is correct

Subtask #4
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	9840 KB	Output is correct
2	Correct	26 ms	9980 KB	Output is correct
3	Correct	49 ms	10308 KB	Output is correct
4	Correct	49 ms	10308 KB	Output is correct
5	Correct	53 ms	9840 KB	Output is correct
6	Correct	93 ms	10692 KB	Output is correct
7	Correct	89 ms	9980 KB	Output is correct
8	Correct	173 ms	10692 KB	Output is correct
9	Correct	406 ms	11460 KB	Output is correct
10	Correct	246 ms	9840 KB	Output is correct
11	Correct	246 ms	10112 KB	Output is correct
12	Correct	286 ms	11460 KB	Output is correct
13	Correct	299 ms	11460 KB	Output is correct

답안 #25931

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 15.0 / 15.0

Subtask #3 20.0 / 20.0

Subtask #4 50.0 / 50.0

Subtask #1
15.0 / 15.0

Subtask #2
15.0 / 15.0

Subtask #3
20.0 / 20.0

Subtask #4
50.0 / 50.0