oj.uz

Submission #155825

# Submission time Handle Problem Language Result Execution time Memory
155825 2019-09-30T16:57:02 Z Akashi Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 6928 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 solve(int sgn, int x, int y, int val){
    int st = x, dr = y;

    while(st <= dr){
        int mij = (st + dr) / 2;

        if(sgn == 1){
            int val2 = query(mij, dr);
            if(val2 > val) dr = mij - 1;
            else st = mij + 1;
        }
        else{
            int val2 = query(st, mij);
            if(val2 > val) st = mij + 1;
            else dr = mij - 1;
        }
    }

    if(sgn == 1) return st;
    return dr;
}

int main()
{
//    freopen("1.in", "r", stdin);

    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 = solve(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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 914 ms 680 KB Output isn't correct
2 Incorrect 1049 ms 760 KB Output isn't correct
3 Incorrect 942 ms 672 KB Output isn't correct
4 Incorrect 1141 ms 764 KB Output isn't correct
5 Incorrect 1050 ms 1016 KB Output isn't correct
6 Incorrect 1037 ms 1016 KB Output isn't correct
7 Incorrect 1043 ms 1116 KB Output isn't correct
8 Incorrect 1286 ms 1108 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 597 ms 3552 KB Output isn't correct
2 Incorrect 578 ms 3452 KB Output isn't correct
3 Incorrect 559 ms 3416 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 719 ms 6120 KB Output isn't correct
6 Incorrect 714 ms 6264 KB Output isn't correct
7 Incorrect 685 ms 5880 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 564 KB Output isn't correct
2 Incorrect 108 ms 640 KB Output isn't correct
3 Incorrect 266 ms 1860 KB Output isn't correct
4 Incorrect 282 ms 1912 KB Output isn't correct
5 Incorrect 289 ms 760 KB Output isn't correct
6 Incorrect 541 ms 2088 KB Output isn't correct
7 Incorrect 482 ms 1080 KB Output isn't correct
8 Incorrect 505 ms 2844 KB Output isn't correct
9 Execution timed out 2065 ms 6928 KB Time limit exceeded
10 Incorrect 956 ms 1500 KB Output isn't correct
11 Incorrect 1516 ms 2468 KB Output isn't correct
12 Execution timed out 2056 ms 6752 KB Time limit exceeded
13 Execution timed out 2067 ms 6772 KB Time limit exceeded