Submission #1309950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309950		jg86	팀들 (IOI15_teams)	C++17	Compilation error	0 ms	0 KiB

teams

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int l, r;
    int sum;
};

static int N;
static vector<int> roots;
static vector<Node> seg;
static size_t baseSizeAfterInit;

static inline int clone_node(int from) {
    seg.push_back(seg[from]);
    return (int)seg.size() - 1;
}

static int update_point(int node, int l, int r, int pos) {
    int n = clone_node(node);
    if (l == r) {
        seg[n].sum++;
        return n;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) seg[n].l = update_point(seg[n].l, l, mid, pos);
    else seg[n].r = update_point(seg[n].r, mid + 1, r, pos);
    seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
    return n;
}

static int query_diff(int pref, int used, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return seg[pref].sum - seg[used].sum;
    int mid = (l + r) >> 1;
    return query_diff(seg[pref].l, seg[used].l, l, mid, ql, qr) +
           query_diff(seg[pref].r, seg[used].r, mid + 1, r, ql, qr);
}

static int consume_suffix(int pref, int used, int l, int r, int start, int &need) {
    if (need == 0 || r < start) return used;

    if (l >= start) {
        int avail = seg[pref].sum - seg[used].sum;
        if (avail == 0) return used;
        if (avail <= need) {
            need -= avail;
            return pref;
        }
        if (l == r) {
            int n = clone_node(used);
            seg[n].sum += need;
            need = 0;
            return n;
        }
    }

    if (l == r) return used;

    int mid = (l + r) >> 1;
    int n = clone_node(used);

    if (start <= mid)
        seg[n].l = consume_suffix(seg[pref].l, seg[used].l, l, mid, start, need);
    else
        seg[n].l = seg[used].l;

    seg[n].r = consume_suffix(seg[pref].r, seg[used].r, mid + 1, r, start, need);
    seg[n].sum = seg[seg[n].l].sum + seg[seg[n].r].sum;
    return n;
}

void init(int N_, int A[], int B[]) {
    N = N_;

    vector<pair<int,int>> students;
    students.reserve(N);
    for (int i = 0; i < N; i++) students.push_back({A[i], B[i]});
    sort(students.begin(), students.end());

    size_t reserveNodes = 1ull + 20ull * (size_t)N + 8000000ull;
    seg.clear();
    seg.reserve(reserveNodes);
    seg.push_back({0, 0, 0});

    roots.assign(N + 1, 0);
    int idx = 0;
    for (int s = 1; s <= N; s++) {
        int root = roots[s - 1];
        while (idx < N && students[idx].first == s) {
            root = update_point(root, 1, N, students[idx].second);
            idx++;
        }
        roots[s] = root;
    }

    baseSizeAfterInit = seg.size();
}

int can(int M, int K[]) {
    vector<int> v;
    v.reserve(M);

    long long total = 0;
    for (int i = 0; i < M; i++) {
        v.push_back(K[i]);
        total += K[i];
        if (total > N) return 0;
    }

    sort(v.begin(), v.end());

    int used = 0;

    for (int i = 0; i < M; ) {
        int s = v[i];
        int cnt = 1;
        while (i + cnt < M && v[i + cnt] == s) cnt++;

        long long need_ll = 1LL * s * cnt;
        int need = (int)need_ll;

        int pref = roots[s];
        int avail = query_diff(pref, used, 1, N, s, N);
        if (avail < need) {
            seg.resize(baseSizeAfterInit);
            return 0;
        }

        int rem = need;
        used = consume_suffix(pref, used, 1, N, s, rem);

        i += cnt;
    }

    seg.resize(baseSizeAfterInit);
    return 1;
}

struct FastScanner {
    static constexpr int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char read() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

    int nextInt() {
        char c;
        do {
            c = read();
            if (!c) return 0;
        } while (c <= ' ');
        int x = 0;
        while (c > ' ') {
            x = x * 10 + (c - '0');
            c = read();
        }
        return x;
    }
};

int main() {
    FastScanner fs;

    int n = fs.nextInt();
    if (!n) return 0;
    vector<int> A(n), B(n);
    for (int i = 0; i < n; i++) {
        A[i] = fs.nextInt();
        B[i] = fs.nextInt();
    }

    init(n, A.data(), B.data());

    int Q = fs.nextInt();
    string out;
    out.reserve(Q * 2);
    vector<int> K;

    for (int qi = 0; qi < Q; qi++) {
        int M = fs.nextInt();
        K.resize(M);
        for (int i = 0; i < M; i++) K[i] = fs.nextInt();
        int ans = can(M, K.data());
        out.push_back(char('0' + ans));
        out.push_back('\n');
    }

    fwrite(out.c_str(), 1, out.size(), stdout);
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccsiav2a.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyGIV5R.o:teams.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status