oj.uz

Submission #93392

# Submission time Handle Problem Language Result Execution time Memory
93392 2019-01-08T04:27:33 Z RezwanArefin01 Cake (CEOI14_cake) C++17
0 / 100
 297 ms 4216 KB 
///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 2e5 + 10; 

struct tree {
    vector<int> bit;
    int N, lg;
    void init(int n) { 
        N = n; lg = log2(N) + 1; 
        bit = vector<int> (n + 1,  0); 
    }
    void update(int x, int v) {
        for(; x <= N; x += x & -x) 
            bit[x] = max(bit[x], v); 
    }
    int query(int x) { int ret = 0;  
        for(; x > 0; x -= x & -x) 
            ret = max(ret, bit[x]); 
        return ret; 
    }
    int get(int X) {
        int pos = 0, cur = 0;
        for(int i = lg; i >= 0; --i) if((pos | (1 << i)) <= N) {
            if(max(cur, bit[pos | (1 << i)]) <= X) {
                cur = max(cur, bit[pos + (1 << i)]); 
                pos |= 1 << i;
            }
        } return pos; 
    }
} t1, t2;

int n, a, d[N], mn; 
vector<int> p(12, -1); 

int main() {
    scanf("%d %d", &n, &a);  
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &d[i]); 
        if(d[i] > n - 10) {
            p[n - d[i] + 1] = i; 
            mn = min(mn, d[i]); 
        }
    }
    
    int n1 = a, n2 = n - a + 1; 
    t1.init(n1); t2.init(n2); 

    auto upd = [&](int i, int x) {
        if(i <= a) t1.update(a - i + 1, x);
        if(i >= a) t2.update(i - a + 1, x);
    };
    
    for(int i = 1; i <= n; ++i) upd(i, d[i]); 

    int q; scanf("%d", &q); while(q--) {
        char c; int x, e; 
        scanf(" %c", &c); 
        if(c == 'E') {
            scanf("%d %d", &x, &e); 
            int X = d[p[10]]; 
            p.insert(p.begin() + e, x); 
            for(int i = 1; i <= 10; ++i) if(i != e && p[i] == x) 
                { p.erase(p.begin() + i); break; } 
            for(int i = 10; i >= 1; --i) {
                d[p[i]] = X + 11 - i; 
                upd(p[i], d[p[i]]); 
            } p.resize(12);                 
        } else {
            scanf("%d", &x); 
            int X; 
            if(x == a) { puts("0"); continue; }
            if(x < a) X = t2.get(t1.query(a - x + 1));  
            else      X = t1.get(t2.query(x - a + 1));  
            printf("%d\n", abs(x - a) + X - 1); 
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:41: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:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]); 
         ~~~~~^~~~~~~~~~~~~
cake.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int q; scanf("%d", &q); while(q--) {
            ~~~~~^~~~~~~~~~
cake.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c); 
         ~~~~~^~~~~~~~~~~
cake.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &x, &e); 
             ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x); 
             ~~~~~^~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 376 KB Output is correct
2 Incorrect 202 ms 376 KB Output isn't correct
3 Correct 203 ms 440 KB Output is correct
4 Correct 206 ms 440 KB Output is correct
5 Correct 231 ms 508 KB Output is correct
6 Incorrect 249 ms 556 KB Output isn't correct
7 Correct 217 ms 564 KB Output is correct
8 Correct 220 ms 560 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1656 KB Output is correct
2 Incorrect 46 ms 1656 KB Output isn't correct
3 Incorrect 44 ms 1772 KB Output isn't correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 Runtime error 26 ms 1912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 28 ms 2168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 38 ms 3260 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 504 KB Output isn't correct
2 Incorrect 22 ms 504 KB Output isn't correct
3 Incorrect 40 ms 1016 KB Output isn't correct
4 Incorrect 40 ms 936 KB Output isn't correct
5 Incorrect 59 ms 632 KB Output isn't correct
6 Incorrect 74 ms 1280 KB Output isn't correct
7 Incorrect 80 ms 888 KB Output isn't correct
8 Correct 114 ms 1276 KB Output is correct
9 Runtime error 30 ms 4216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 190 ms 1560 KB Output isn't correct
11 Incorrect 209 ms 1784 KB Output isn't correct
12 Correct 297 ms 3516 KB Output is correct
13 Runtime error 28 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)