oj.uz

Submission #57864

# Submission time Handle Problem Language Result Execution time Memory
57864 2018-07-16T12:40:05 Z gabrielsimoes Cake (CEOI14_cake) C++17
100 / 100
 495 ms 72740 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 250010, MAXQ = 500010;
typedef pair<int, int> pii;

struct Bit {
    int sz;
    vector<int> v;

    Bit() : sz(0), v(MAXN) {};

    void resize(int x) {
        sz = x;
    }

    int get(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret = max(ret, v[pos]);
            pos -= pos&-pos;
        }
        return ret;
    }

    void update(int pos, int val) {
        while (pos <= sz) {
            v[pos] = max(v[pos], val);
            pos += pos&-pos;
        }
    }

    int find(int val) {
        int ret = 0;
        for (int i = 20; i >= 0; i--) {
            int nx = ret + (1 << i);
            if (nx <= sz && v[nx] < val) {
                ret = nx;
            }
        }
        return ret;
    }
} l, r;

int n, start;
int d[MAXN];

int inTop10[MAXN];
int top_change = 0;
vector<pii> top10;

int main() {
    scanf("%d%d", &n, &start);
    for (int i = 1; i <= n; i++)
        scanf("%d", &d[i]);

    for (int i = 1; i <= n; i++)
        top10.push_back({d[i], i});

    l.resize(start - 1);
    r.resize(n - start);

    for (int i = start-1; i >= 1; i--) {
        l.update(start - i, d[i]);
    }

    for (int i = start+1; i <= n; i++) {
        r.update(i - start, d[i]);
    }

    sort(top10.rbegin(), top10.rend());
    top10.resize(min(n, 10));
    memset(inTop10, -1, sizeof(inTop10));
    for (int i = 0; i < top10.size(); i++)
        inTop10[top10[i].second] = i;

    top_change = n+1;

    char c;
    int nq, x, y;
    scanf("%d", &nq);
    while (nq--) {
        scanf(" %c", &c);
        if (c == 'E') {
            scanf("%d%d", &x, &y);

            if (inTop10[x] != -1) {
                top10.erase(top10.begin() + inTop10[x]);
                inTop10[x] = -1;
            }

            for (pii p : top10) inTop10[p.second] = -1;

            top10.insert(top10.begin() + (y-1), {-1, x});
            top10.resize(min(n, 10));

            for (int i = int(top10.size()) - 1; i >= 0; i--) {
                pii &p = top10[i];

                // printf("changing pos %d to %d\n", p.second, top_change);
                p.first = top_change++;
                inTop10[p.second] = i;

                if (p.second < start) l.update(start - p.second, p.first);
                if (p.second > start) r.update(p.second - start, p.first);
            }
        } else {
            scanf("%d", &x);

            if (x == start) {
                printf("%d\n", 0);
                continue;
            }

            int pos = abs(start - x), mx, cnt;
            if (x < start) {
                mx = l.get(pos);
                cnt = r.find(mx+1);
            } else {
                mx = r.get(pos);
                cnt = l.find(mx+1);
            }

            // printf("pos %d (%c) mx %d cnt %d\n", pos, x < start ? 'l' : 'r', mx, cnt);

            printf("%d\n", pos + cnt);
        }
    }
}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < top10.size(); i++)
                     ~~^~~~~~~~~~~~~~
cake.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &start);
     ~~~~~^~~~~~~~~~~~~~~~~~~~
cake.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &d[i]);
         ~~~~~^~~~~~~~~~~~~
cake.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &nq);
     ~~~~~^~~~~~~~~~~
cake.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
         ~~~~~^~~~~~~~~~~
cake.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
cake.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3192 KB Output is correct
2 Correct 6 ms 3304 KB Output is correct
3 Correct 5 ms 3464 KB Output is correct
4 Correct 9 ms 3544 KB Output is correct
5 Correct 12 ms 3832 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 7712 KB Output is correct
2 Correct 381 ms 11800 KB Output is correct
3 Correct 319 ms 15796 KB Output is correct
4 Correct 495 ms 19856 KB Output is correct
5 Correct 381 ms 24476 KB Output is correct
6 Correct 386 ms 29108 KB Output is correct
7 Correct 312 ms 33628 KB Output is correct
8 Correct 399 ms 38252 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 40480 KB Output is correct
2 Correct 113 ms 40864 KB Output is correct
3 Correct 133 ms 41392 KB Output is correct
4 Correct 5 ms 41392 KB Output is correct
5 Correct 202 ms 44068 KB Output is correct
6 Correct 132 ms 44760 KB Output is correct
7 Correct 151 ms 45184 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 45184 KB Output is correct
2 Correct 30 ms 45184 KB Output is correct
3 Correct 66 ms 45184 KB Output is correct
4 Correct 87 ms 45184 KB Output is correct
5 Correct 76 ms 45184 KB Output is correct
6 Correct 110 ms 45756 KB Output is correct
7 Correct 103 ms 46396 KB Output is correct
8 Correct 187 ms 48736 KB Output is correct
9 Correct 459 ms 56548 KB Output is correct
10 Correct 297 ms 56548 KB Output is correct
11 Correct 292 ms 60672 KB Output is correct
12 Correct 395 ms 67644 KB Output is correct
13 Correct 402 ms 72740 KB Output is correct