oj.uz

Submission #155830

# Submission time Handle Problem Language Result Execution time Memory
155830 2019-09-30T17:33:36 Z Akashi Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 7184 KB 
#include <bits/stdc++.h>
using namespace std;

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

void propag(int nod){
    Lazy[nod * 2] += Lazy[nod];
    Arb[nod * 2] += Lazy[nod];
    Lazy[nod * 2 + 1] += 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;
        Arb[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 = 1e9, a2 = 1e9;
    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);
//    freopen("1.out", "w", stdout);

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

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

                pos[y] = x;
                for(int i = 1; i <= 10 && i <= n ; ++i) update2(pos[i], i);
            }
        }
    }



    return 0;
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:100: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:102: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:109:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
cake.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c", &c);
         ~~~~~^~~~~~~~~~~~
cake.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
cake.cpp:133:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 25 ms 632 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 680 KB Output is correct
2 Correct 710 ms 760 KB Output is correct
3 Correct 680 ms 732 KB Output is correct
4 Correct 694 ms 632 KB Output is correct
5 Correct 790 ms 1016 KB Output is correct
6 Correct 788 ms 1016 KB Output is correct
7 Correct 750 ms 1144 KB Output is correct
8 Correct 772 ms 1216 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 3480 KB Output is correct
2 Correct 503 ms 3328 KB Output is correct
3 Correct 472 ms 3240 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 652 ms 6120 KB Output is correct
6 Correct 717 ms 6124 KB Output is correct
7 Correct 654 ms 5692 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 572 KB Output is correct
2 Correct 98 ms 604 KB Output is correct
3 Correct 260 ms 1936 KB Output is correct
4 Correct 223 ms 1780 KB Output is correct
5 Correct 226 ms 720 KB Output is correct
6 Correct 463 ms 2320 KB Output is correct
7 Correct 334 ms 1272 KB Output is correct
8 Correct 374 ms 2908 KB Output is correct
9 Correct 1969 ms 7160 KB Output is correct
10 Correct 751 ms 1568 KB Output is correct
11 Correct 1091 ms 2568 KB Output is correct
12 Correct 1854 ms 6912 KB Output is correct
13 Execution timed out 2059 ms 7184 KB Time limit exceeded