oj.uz

답안 #155824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155824 2019-09-30T16:40:13 Z Akashi 케이크 (CEOI14_cake) C++14
0 / 100
 1310 ms 8536 KB 
#include <bits/stdc++.h>
using namespace std;

int n, a;
int pos[10];
int x[250005];
int Arb[1000005], Lazy[1000005];

void propag(int nod){
    Lazy[nod * 2] += Lazy[nod];
    Lazy[nod * 2 + 1] += Lazy[nod];
    Arb[nod * 2] += Lazy[nod];
    Arb[nod * 2 + 1] += Lazy[nod];
    Lazy[nod] = 0;
}

void build(int st = 1, int dr = n, int nod = 1){
    if(st == dr){
        Arb[nod] = x[st];
        return ;
    }

    int mij = (st + dr) / 2;

    build(st, mij, nod * 2);
    build(mij + 1, dr, nod * 2 + 1);

    Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}

void update(int x, int y, int v, int st = 1, int dr = n, int nod = 1){
    if(x <= st && dr <= y){
        Lazy[nod] += v;
        return ;
    }
    propag(nod);

    int mij = (st + dr) / 2;
    if(x <= mij) update(x, y, v, st, mij, nod * 2);
    if(mij + 1 <= y) update(x, y, v, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}

void update2(int x, int v, int st = 1, int dr = n, int nod = 1){
    if(st == dr){
        Arb[nod] = v;
        return ;
    }
    propag(nod);

    int mij = (st + dr) / 2;
    if(x <= mij) update2(x, v, st, mij, nod * 2);
    else update2(x, v, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}

int query(int x, int y, int st = 1, int dr = n, int nod = 1){
    if(x <= st && dr <= y) return Arb[nod];
    propag(nod);

    int mij = (st + dr) / 2;
    int a1 = n + 1, a2 = n + 1;
    if(x <= mij) a1 = query(x, y, st, mij, nod * 2);
    if(mij + 1 <= y) a2 = query(x, y, mij + 1, dr, nod * 2 + 1);

    Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
    return min(a1, a2);
}

int query2(int sgn, int x, int y, int val, int st = 1, int dr = n, int nod = 1){
    if(dr < x) return x - 1;
    if(st > y) return y + 1;

    if(st == dr){
        if(Arb[nod] >= val) return st;
        return st + sgn;
    }

    propag(nod);
    int mij = (st + dr) / 2;

    if(sgn == -1){
        if(Arb[nod * 2] >= val) return query2(sgn, x, y, val, mij + 1, dr, nod * 2 + 1);
        return query2(sgn, x, y, val, st, mij, nod * 2);
    }
    else{
        if(Arb[nod * 2 + 1] >= val) return query2(sgn, x, y, val, st, mij, nod * 2);
        return query2(sgn, x, y, val, mij + 1, dr, nod * 2 + 1);
    }

    Arb[nod] = min(Arb[nod * 2], Arb[nod * 2 + 1]);
}

int main()
{
    scanf("%d%d", &n, &a);
    for(int i = 1; i <= n ; ++i){
        scanf("%d", &x[i]), x[i] = n - x[i] + 1;
        if(x[i] <= 10) pos[x[i]] = i;
    }

    build();

    int q;
    scanf("%d", &q);

    char c;
    int x, y;
    while(q--){
        scanf("\n%c", &c);

        if(c == 'F'){
            scanf("%d", &x);
            if(x == a){
                printf("0\n");
                continue ;
            }
            int val = query(min(x, a + 1), max(x, a - 1));

            int st = 1, dr = a - 1, sgn = 1;
            if(x < a) st = a + 1, dr = n, sgn = -1;

            int p = query2(sgn, st, dr, val);
            int Sol = abs(x - a) + abs(p - a);

            printf("%d\n", Sol);
        }
        else{
            scanf("%d%d", &x, &y);

            int p = 11;
            for(int i = 1; i <= 10 ; ++i)
                if(pos[i] == x) p = i;

            if(p == 11){
                update(1, n, 1);
                for(int i = 1; i < y ; ++i) update2(pos[i], i);
                for(int i = 10; i >= y ; --i) pos[i] = pos[i - 1];
                update2(x, y);
                pos[y] = x;
            }
            else{
                if(p == y) continue ;
                for(int i = p; i < 10 ; ++i){
                    if(i >= n) continue ;
                    pos[i] = pos[i + 1];
                    update2(pos[i], i);
                }

                for(int i = 10; i > y ; --i){
                    if(i > n) continue ;
                    pos[i] = pos[i - 1];
                    update2(pos[i], i);
                }

                pos[y] = x;
                update2(x, y);
            }

        }
    }



    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &a);
     ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:100:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x[i]), x[i] = n - x[i] + 1;
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
cake.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &c);
         ~~~~~^~~~~~~~~~~~
cake.cpp:115:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:131:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:135:25: warning: iteration 9 invokes undefined behavior [-Waggressive-loop-optimizations]
                 if(pos[i] == x) p = i;
                    ~~~~~^
cake.cpp:134:30: note: within this loop
             for(int i = 1; i <= 10 ; ++i)
                            ~~^~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 960 ms 2204 KB Output isn't correct
2 Incorrect 1074 ms 2272 KB Output isn't correct
3 Incorrect 952 ms 2368 KB Output isn't correct
4 Incorrect 1149 ms 2260 KB Output isn't correct
5 Incorrect 1033 ms 2408 KB Output isn't correct
6 Incorrect 1054 ms 2296 KB Output isn't correct
7 Incorrect 1047 ms 2476 KB Output isn't correct
8 Incorrect 1310 ms 2432 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 116 ms 4700 KB Output isn't correct
2 Incorrect 109 ms 4712 KB Output isn't correct
3 Incorrect 100 ms 4700 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 153 ms 7632 KB Output isn't correct
6 Incorrect 144 ms 7580 KB Output isn't correct
7 Incorrect 110 ms 7292 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 1016 KB Output isn't correct
2 Incorrect 40 ms 964 KB Output isn't correct
3 Incorrect 84 ms 2680 KB Output isn't correct
4 Incorrect 101 ms 2552 KB Output isn't correct
5 Incorrect 135 ms 1784 KB Output isn't correct
6 Incorrect 161 ms 3576 KB Output isn't correct
7 Incorrect 160 ms 2684 KB Output isn't correct
8 Incorrect 513 ms 4356 KB Output isn't correct
9 Incorrect 811 ms 8536 KB Output isn't correct
10 Incorrect 454 ms 3064 KB Output isn't correct
11 Incorrect 562 ms 3960 KB Output isn't correct
12 Incorrect 796 ms 8132 KB Output isn't correct
13 Incorrect 911 ms 8368 KB Output isn't correct