oj.uz

Submission #391821

# Submission time Handle Problem Language Result Execution time Memory
391821 2021-04-20T03:20:47 Z cheissmart Cake (CEOI14_cake) C++14
100 / 100
 1752 ms 77988 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") ->" << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int d[N], rk[N], vis[N], l[N], r[N], n;
vi G[N], topo;

void dfs(int u) {
    vis[u] = 1;
    for(int v:G[u]) if(!vis[v]) dfs(v);
    topo.PB(u);
}

int t[N * 4];

void upd(int pos, int val, int v = 1, int tl = 0, int tr = n) {
    if(tl >= tr) exit(0);
    if(tr - tl == 1) {
        t[v] = val;
        return;
    }
    int tm = (tl + tr) / 2;
    if(pos < tm) upd(pos, val, v * 2, tl, tm);
    else upd(pos, val, v * 2 + 1, tm, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}


int qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
    if(l <= tl && tr <= r) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    int ans = INF;
    if(l < tm) ans = min(ans, qry(l, r, v * 2, tl, tm));
    if(r > tm) ans = min(ans, qry(l, r, v * 2 + 1, tm, tr));
    return ans;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0);

    int a; cin >> n >> a, a--;
    for(int i = 0; i < n; i++) {
        cin >> d[i];
    }

    vi p(n);
    iota(ALL(p), 0);
    sort(ALL(p), [&] (int a, int b) {
        return d[a] > d[b];
    });

    int q; cin >> q;
    int s = n + q, t = s + 1;

    auto add_edge = [&] (int u, int v) {
        G[u].PB(v);
        r[u] = v;
        l[v] = u;
    };

    for(int i = 1; i < n; i++) add_edge(p[i - 1], p[i]);
    add_edge(s, p[0]);
    add_edge(p[n - 1], t);

    V<array<int, 2>> qq;
    {
        vi who(n);
        iota(ALL(who), 0);

        int new_node = n;
        for(int i = 0; i < q; i++) {
            char op; cin >> op;
            if(op == 'F') {
                int x; cin >> x, x--;
                qq.PB({1, x});
            } else {
                int x, y; cin >> x >> y, x--;
                qq.PB({2, x});
                int u = who[x];
                add_edge(l[u], r[u]);
                u = who[x] = new_node++;
                int ptr = s;
                for(int j = 0; j < y; j++) ptr = r[ptr];
                add_edge(l[ptr], u);
                add_edge(u, ptr);
            }
        }
    }

    dfs(s);
    reverse(ALL(topo));

    for(int i = 0; i < topo.size(); i++) {
        rk[topo[i]] = i;
    }

    {
        for(int i = 0; i < n; i++)
            upd(i, rk[i]);
        int new_node = n;
        for(int i = 0; i < q; i++) {
            if(qq[i][0] == 1) {
                int x = qq[i][1];
                if(x == a) {
                    cout << 0 << '\n';
                } else if(x > a) {
                    int mn = qry(a + 1, x + 1);
                    int lb = 0, rb = a - 1;
                    while(lb <= rb) {
                        int mb = (lb + rb) / 2;
                        if(qry(mb, a) > mn) rb = mb - 1;
                        else lb = mb + 1;
                    }
                    cout << x - lb << '\n';
                } else {
                    int mn = qry(x, a);
                    int lb = a + 1, rb = n - 1;
                    while(lb <= rb) {
                        int mb = (lb + rb) / 2;
                        if(qry(a + 1, mb + 1) < mn) rb = mb - 1;
                        else lb = mb + 1;
                    }
                    cout << rb - x << '\n';
                }
            } else {
                int x = qq[i][1];
                upd(x, rk[new_node++]);
            }
        }
    }

}

Compilation message

cake.cpp: In function 'int main()':
cake.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i = 0; i < topo.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23756 KB Output is correct
2 Correct 16 ms 23756 KB Output is correct
3 Correct 17 ms 23816 KB Output is correct
4 Correct 20 ms 24140 KB Output is correct
5 Correct 35 ms 25616 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 58552 KB Output is correct
2 Correct 243 ms 58748 KB Output is correct
3 Correct 274 ms 58540 KB Output is correct
4 Correct 220 ms 58668 KB Output is correct
5 Correct 350 ms 59988 KB Output is correct
6 Correct 323 ms 59948 KB Output is correct
7 Correct 316 ms 59976 KB Output is correct
8 Correct 236 ms 60208 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 37900 KB Output is correct
2 Correct 363 ms 37792 KB Output is correct
3 Correct 369 ms 37812 KB Output is correct
4 Correct 15 ms 23756 KB Output is correct
5 Correct 567 ms 55604 KB Output is correct
6 Correct 659 ms 55664 KB Output is correct
7 Correct 537 ms 55584 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 26556 KB Output is correct
2 Correct 92 ms 26844 KB Output is correct
3 Correct 217 ms 33396 KB Output is correct
4 Correct 180 ms 33368 KB Output is correct
5 Correct 164 ms 30576 KB Output is correct
6 Correct 443 ms 38512 KB Output is correct
7 Correct 289 ms 33512 KB Output is correct
8 Correct 232 ms 48280 KB Output is correct
9 Correct 1431 ms 77620 KB Output is correct
10 Correct 575 ms 44180 KB Output is correct
11 Correct 793 ms 48832 KB Output is correct
12 Correct 1421 ms 72304 KB Output is correct
13 Correct 1752 ms 77988 KB Output is correct