oj.uz

Submission #155942

# Submission time Handle Problem Language Result Execution time Memory
155942 2019-10-02T06:54:00 Z Akashi Cake (CEOI14_cake) C++14
83.3333 / 100
 2000 ms 12796 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 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 23 ms 760 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 5012 KB Output is correct
2 Correct 560 ms 5116 KB Output is correct
3 Correct 603 ms 4984 KB Output is correct
4 Correct 534 ms 4880 KB Output is correct
5 Correct 885 ms 5624 KB Output is correct
6 Correct 666 ms 6068 KB Output is correct
7 Correct 667 ms 5752 KB Output is correct
8 Correct 588 ms 5724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 4728 KB Output is correct
2 Correct 370 ms 4728 KB Output is correct
3 Correct 345 ms 4528 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 499 ms 8568 KB Output is correct
6 Correct 542 ms 8656 KB Output is correct
7 Correct 487 ms 6384 KB Output is correct

Subtask #4
33.333333 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 932 KB Output is correct
2 Correct 90 ms 988 KB Output is correct
3 Correct 229 ms 2936 KB Output is correct
4 Correct 206 ms 2936 KB Output is correct
5 Correct 217 ms 1784 KB Output is correct
6 Correct 410 ms 3692 KB Output is correct
7 Correct 296 ms 2836 KB Output is correct
8 Correct 357 ms 5368 KB Output is correct
9 Correct 1819 ms 12796 KB Output is correct
10 Correct 717 ms 5252 KB Output is correct
11 Correct 999 ms 6704 KB Output is correct
12 Correct 1690 ms 12452 KB Output is correct
13 Execution timed out 2001 ms 12648 KB Time limit exceeded