Submission #1178832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178832		anmattroi	Teams (IOI15_teams)	C++17	0 / 100	428 ms	156604 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define maxn 500005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n;
int a[maxn], b[maxn], dp[maxn];
int it[22*maxn], L[22*maxn], R[22*maxn], root[maxn], nt = 0;

int build(int lo = 1, int hi = n) {
    if (lo == hi) return ++nt;
    int cur = ++nt, mid = (lo + hi) >> 1;
    L[cur] = build(lo, mid);
    R[cur] = build(mid+1, hi);
    return cur;
}

int upd(int u, int oldver, int lo = 1, int hi = n) {
    if (lo == hi) {
        it[++nt] = it[oldver] + 1;
        return nt;
    }
    int cur = ++nt, mid = (lo + hi) >> 1;
    if (u <= mid) {
        L[cur] = upd(u, L[oldver], lo, mid);
        R[cur] = R[oldver];
    } else {
        L[cur] = L[oldver];
        R[cur] = upd(u, R[oldver], mid+1, hi);
    }
    it[cur] = it[L[cur]] + it[R[cur]];
    return cur;
}

int get(int u, int v, int r, int lo = 1, int hi = n) {
    if (u <= lo && hi <= v) return it[r];
    int mid = (lo + hi) >> 1;
    return (u <= mid ? get(u, v, L[r], lo, mid) : 0) +
           (v > mid ? get(u, v, R[r], mid+1, hi) : 0);
}

vector<int> adj[maxn];

void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 0; i < N; i++) a[i] = A[i];
    for (int i = 0; i < N; i++) b[i] = B[i];
    for (int i = 0; i < N; i++) adj[a[i]].emplace_back(b[i]);
    sort(a, a + N);
    sort(b, b + N);
    root[0] = build();
    for (int i = 1; i <= N; i++) {
        root[i] = root[i-1];
        for (int j : adj[i]) root[i] = upd(j, root[i]);
    }
}

int can(int M, int K[]) {
    vector<int> Stack;
    sort(K, K+M);
    int64_t sum = 0;
    for (int i = 0; i < M; i++) sum += K[i];
    if (sum > n) return 0;

    function<int(int, int)> cost = [&](int u, int v) {
        return dp[u] + get(K[v], n, root[K[v]]) - get(K[v], n, root[K[u]]) - K[v];
    };

    for (int i = 0; i < M; i++) {
        if (Stack.empty()) {
            dp[i] = get(K[i], n, root[K[i]]) - K[i];
            Stack.emplace_back(i);
            continue;
        }
        while (Stack.size() >= 2 && cost(Stack[Stack.size()-2], i) <= cost(Stack[Stack.size()-1], i)) Stack.pop_back();
        dp[i] = cost(Stack.back(), i);
    }

    int ans = INT_MAX;
    for (int i = 0; i < M; i++) ans = min(ans, dp[i]);
    return ans >= 0;
}

/*
4
1 2
2 3
2 3
2 4
2
2 1 3
2 1 1
*/

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23