Submission #1207266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207266		anonymous321	Teams (IOI15_teams)	C++20	34 / 100	4094 ms	31684 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int>::max()/4;
typedef long long ll;

vector<int> va, vb;
int n;

struct st {
    vector<int> v, lazy;
    int as;
};

void push (st &seg, int i) {
    int d = seg.lazy[i];
    seg.lazy[i*2] += d;
    seg.v[i*2] += d;
    seg.lazy[i*2 + 1] += d;
    seg.v[i*2 + 1] += d;
    seg.lazy[i] = 0;
}

st build (int n) {
    int as = 1 << (__lg(n) + 1);
    vector<int> v (as*2, INF);
    vector<int> lazy (as*2, 0);
    return {v, lazy, as};
}

int query (st &seg, int l, int r, int i = 1, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (lo >= r || hi <= l) return INF;
    if (l <= lo && hi <= r) return seg.v[i];
    push(seg, i);
    int mid = (lo + hi) / 2;
    int q1 = query(seg, l, r, i*2, lo, mid);
    int q2 = query(seg, l, r, i*2 + 1, mid, hi);
    return min(q1, q2);
}

void update (st &seg, int id, int x, int i = 1, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (lo == hi-1) {
        seg.v[i] = x;
        return;
    }
    push(seg, i);
    int mid = (lo + hi) / 2;
    if (id < mid) {
        update(seg, id, x, i*2, lo, mid);
    } else {
        update(seg, id, x, i*2 + 1, mid, hi);
    }
    seg.v[i] = min(seg.v[i*2], seg.v[i*2 + 1]);
}

void apply (st &seg, int l, int r, int d, int i = 1, int lo = 0, int hi = -1) {
    if (hi == -1) hi = seg.as;
    if (lo >= r || hi <= l) return;
    if (l <= lo && hi <= r) {
        seg.lazy[i] += d;
        seg.v[i] += d;
        return;
    }
    push(seg, i);
    int mid = (lo + hi) / 2;
    apply(seg, l, r, d, i*2, lo, mid);
    apply(seg, l, r, d, i*2 + 1, mid, hi);
    seg.v[i] = min(seg.v[i*2], seg.v[i*2 + 1]);
}

void init(int N, int A[], int B[]) {
    vector<pair<int, int>> vq {};
    for (int i = 0; i < N; i++) {
        vq.push_back({A[i], B[i]});
    }
    sort(vq.begin(), vq.end());
    for (int i = 0; i < N; i++) {
        va.push_back(vq[i].first);
        vb.push_back(vq[i].second);
    }
    n = N;
}

int can(int M, int K[]) {
    map<int, int> ts {};
    ll total = 0;
    for (int i = 0; i < M; i++) {
        ts[K[i]] += 1;
        total += K[i];
    }
    if (total > n) return 0;

    int m = ts.size();
    vector<int> vk {};
    vector<int> vc {};
    for (auto [k, s] : ts) {
        vk.push_back(k);
        vc.push_back(k*s);
    }

    bool possible = true;
    st seg = build (m+1);
    update(seg, 0, n);
    int id = 0; // student
    set<pair<int, int>> s {}; // b, student id
    for (int i = 0; i < m; i++) {
        while (id < n && va[id] <= vk[i]) {
            s.insert({vb[id], id});
            id++;
        }
        while (!s.empty() && s.begin()->first < vk[i]) {
            auto[b, rid] = *s.begin();
            int a = va[rid];
            auto it = lower_bound(vk.begin(), vk.end(), a);
            apply(seg, 0, distance(vk.begin(), it) + 1, -1);
            s.erase(s.begin());
        }
        int sol = query(seg, 0, i+1) - vc[i];
        update(seg, i+1, sol);
        if (sol - n + id < 0) return 0;
    }
    return 1;
}

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