oj.uz

Submission #155826

# Submission time Handle Problem Language Result Execution time Memory
155826 2019-09-30T16:59:49 Z Akashi Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 6728 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, y);
            if(val2 > val) dr = mij - 1;
            else st = mij + 1;
        }
        else{
            int val2 = query(x, 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 927 ms 732 KB Output isn't correct
2 Incorrect 1045 ms 760 KB Output isn't correct
3 Incorrect 947 ms 760 KB Output isn't correct
4 Incorrect 1220 ms 804 KB Output isn't correct
5 Incorrect 1024 ms 888 KB Output isn't correct
6 Incorrect 1037 ms 1144 KB Output isn't correct
7 Incorrect 1064 ms 1016 KB Output isn't correct
8 Incorrect 1295 ms 1200 KB Output isn't correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 730 ms 3428 KB Output isn't correct
2 Incorrect 695 ms 3616 KB Output isn't correct
3 Incorrect 738 ms 3320 KB Output isn't correct
4 Incorrect 2 ms 376 KB Output isn't correct
5 Incorrect 862 ms 5980 KB Output isn't correct
6 Incorrect 865 ms 6060 KB Output isn't correct
7 Incorrect 789 ms 6016 KB Output isn't correct

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 656 KB Output isn't correct
2 Incorrect 121 ms 632 KB Output isn't correct
3 Incorrect 305 ms 1912 KB Output isn't correct
4 Incorrect 303 ms 1820 KB Output isn't correct
5 Incorrect 316 ms 768 KB Output isn't correct
6 Incorrect 607 ms 2168 KB Output isn't correct
7 Incorrect 537 ms 1236 KB Output isn't correct
8 Incorrect 507 ms 2908 KB Output isn't correct
9 Execution timed out 2058 ms 6728 KB Time limit exceeded
10 Incorrect 1044 ms 1564 KB Output isn't correct
11 Incorrect 1693 ms 2468 KB Output isn't correct
12 Execution timed out 2021 ms 6600 KB Time limit exceeded
13 Execution timed out 2039 ms 6620 KB Time limit exceeded