oj.uz

Submission #155831

# Submission time Handle Problem Language Result Execution time Memory
155831 2019-09-30T17:34:16 Z Akashi Cake (CEOI14_cake) C++14
100 / 100
 1963 ms 7156 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 ;
    }
    if(Lazy[nod]) 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 ;
    }
    if(Lazy[nod]) 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];
    if(Lazy[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 668 ms 668 KB Output is correct
2 Correct 551 ms 672 KB Output is correct
3 Correct 595 ms 716 KB Output is correct
4 Correct 530 ms 548 KB Output is correct
5 Correct 734 ms 984 KB Output is correct
6 Correct 655 ms 988 KB Output is correct
7 Correct 657 ms 988 KB Output is correct
8 Correct 580 ms 760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 3368 KB Output is correct
2 Correct 367 ms 3232 KB Output is correct
3 Correct 337 ms 3320 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 493 ms 6008 KB Output is correct
6 Correct 537 ms 6192 KB Output is correct
7 Correct 491 ms 3740 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 504 KB Output is correct
2 Correct 89 ms 540 KB Output is correct
3 Correct 223 ms 1784 KB Output is correct
4 Correct 205 ms 1836 KB Output is correct
5 Correct 215 ms 760 KB Output is correct
6 Correct 406 ms 2156 KB Output is correct
7 Correct 351 ms 1160 KB Output is correct
8 Correct 354 ms 2808 KB Output is correct
9 Correct 1775 ms 7156 KB Output is correct
10 Correct 711 ms 1544 KB Output is correct
11 Correct 989 ms 2448 KB Output is correct
12 Correct 1674 ms 6884 KB Output is correct
13 Correct 1963 ms 7140 KB Output is correct