oj.uz

Submission #93391

# Submission time Handle Problem Language Result Execution time Memory
93391 2019-01-08T03:32:25 Z RezwanArefin01 Cake (CEOI14_cake) C++17
0 / 100
 249 ms 9592 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], p[20]; 

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; 
    }
    
    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); 
            d[x] = d[p[e]]; 
            for(int i = 10 ; i > e; i--) 
                p[i] = p[i - 1]; 
            p[e] = x;
            for(int i = e; i >= 1; i--) 
                upd(p[i], ++d[p[i]]); 
        } 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:40: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:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]); 
         ~~~~~^~~~~~~~~~~~~
cake.cpp:57: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:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c); 
         ~~~~~^~~~~~~~~~~
cake.cpp:61: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:69: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 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 141 ms 4856 KB Output isn't correct
2 Incorrect 145 ms 4856 KB Output isn't correct
3 Correct 130 ms 4856 KB Output is correct
4 Correct 112 ms 4856 KB Output is correct
5 Incorrect 149 ms 5240 KB Output isn't correct
6 Incorrect 160 ms 5496 KB Output isn't correct
7 Correct 130 ms 5368 KB Output is correct
8 Correct 120 ms 5556 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 3064 KB Output is correct
2 Incorrect 45 ms 2908 KB Output isn't correct
3 Incorrect 44 ms 3064 KB Output isn't correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Runtime error 27 ms 3548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 29 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 40 ms 4856 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 19 ms 888 KB Output isn't correct
2 Incorrect 18 ms 892 KB Output isn't correct
3 Incorrect 33 ms 1912 KB Output isn't correct
4 Incorrect 36 ms 1912 KB Output isn't correct
5 Incorrect 52 ms 1912 KB Output isn't correct
6 Incorrect 58 ms 2908 KB Output isn't correct
7 Incorrect 62 ms 2552 KB Output isn't correct
8 Correct 72 ms 3704 KB Output is correct
9 Runtime error 30 ms 5720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 167 ms 5288 KB Output isn't correct
11 Incorrect 188 ms 6052 KB Output isn't correct
12 Incorrect 249 ms 9592 KB Output isn't correct
13 Runtime error 29 ms 4092 KB Execution killed with signal 11 (could be triggered by violating memory limits)