Submission #391821

#	Time	Username	Problem	Language	Result	Execution time	Memory
391821		cheissmart	Cake (CEOI14_cake)	C++14	100 / 100	1752 ms	77988 KiB

cake

#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 (stderr)

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 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50