답안 #25970 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
25970	2017-06-25T09:06:08 Z	tlwpdus	케이크 (CEOI14_cake)	C++	100 / 100	446 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	246 ms	9980 KB	Output is correct
2	Correct	196 ms	9980 KB	Output is correct
3	Correct	193 ms	9980 KB	Output is correct
4	Correct	156 ms	9980 KB	Output is correct
5	Correct	189 ms	10112 KB	Output is correct
6	Correct	209 ms	10112 KB	Output is correct
7	Correct	206 ms	10112 KB	Output is correct
8	Correct	176 ms	10112 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	99 ms	10692 KB	Output is correct
2	Correct	93 ms	10692 KB	Output is correct
3	Correct	79 ms	10692 KB	Output is correct
4	Correct	0 ms	9840 KB	Output is correct
5	Correct	166 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
50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	9840 KB	Output is correct
2	Correct	16 ms	9980 KB	Output is correct
3	Correct	46 ms	10308 KB	Output is correct
4	Correct	46 ms	10308 KB	Output is correct
5	Correct	63 ms	9840 KB	Output is correct
6	Correct	103 ms	10692 KB	Output is correct
7	Correct	83 ms	9980 KB	Output is correct
8	Correct	129 ms	10692 KB	Output is correct
9	Correct	446 ms	11460 KB	Output is correct
10	Correct	206 ms	9840 KB	Output is correct
11	Correct	219 ms	10112 KB	Output is correct
12	Correct	303 ms	11460 KB	Output is correct
13	Correct	303 ms	11460 KB	Output is correct

답안 #25970

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