oj.uz

답안 #155764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155764 2019-09-30T12:20:27 Z Akashi 케이크 (CEOI14_cake) C++14
0 / 100
 1295 ms 13440 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);

    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;
    }

    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);
    }
}

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:94: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:96: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:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
cake.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &c);
         ~~~~~^~~~~~~~~~~~
cake.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:127: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:131:25: warning: iteration 9 invokes undefined behavior [-Waggressive-loop-optimizations]
                 if(pos[i] == x) p = i;
                    ~~~~~^
cake.cpp:130: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 903 ms 5112 KB Output isn't correct
2 Incorrect 1041 ms 5172 KB Output isn't correct
3 Incorrect 940 ms 5240 KB Output isn't correct
4 Incorrect 1128 ms 5244 KB Output isn't correct
5 Incorrect 1037 ms 5708 KB Output isn't correct
6 Incorrect 1027 ms 5964 KB Output isn't correct
7 Incorrect 1036 ms 5836 KB Output isn't correct
8 Incorrect 1295 ms 6064 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 101 ms 4728 KB Output isn't correct
2 Incorrect 96 ms 4688 KB Output isn't correct
3 Incorrect 89 ms 4728 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 141 ms 8540 KB Output isn't correct
6 Incorrect 139 ms 8604 KB Output isn't correct
7 Incorrect 101 ms 8312 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 924 KB Output isn't correct
2 Incorrect 38 ms 1140 KB Output isn't correct
3 Incorrect 71 ms 2680 KB Output isn't correct
4 Incorrect 91 ms 2680 KB Output isn't correct
5 Incorrect 129 ms 1820 KB Output isn't correct
6 Incorrect 141 ms 3736 KB Output isn't correct
7 Incorrect 145 ms 2680 KB Output isn't correct
8 Incorrect 486 ms 5284 KB Output isn't correct
9 Incorrect 698 ms 13432 KB Output isn't correct
10 Incorrect 416 ms 5240 KB Output isn't correct
11 Incorrect 516 ms 6776 KB Output isn't correct
12 Incorrect 704 ms 12764 KB Output isn't correct
13 Incorrect 825 ms 13440 KB Output isn't correct