Submission #374760

#	Time	Username	Problem	Language	Result	Execution time	Memory
374760		ijxjdjd	Teams (IOI15_teams)	C++14	34 / 100	4094 ms	374560 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int MAXN = (int)(5e5);
const int MAXQ = (int)(1e5) + 5;
vector<pair<int, int>> vec;
multiset<pair<int, int>> mn[4*MAXQ];
int N;
void upd(int id, bool er, int n = 1, int tl = 0, int tr = MAXQ-1) {
    if (er) {
        mn[n].erase({vec[id].first, id});
    }
    else {
        mn[n].insert({vec[id].first, id});
    }
    if (tl == tr) {
        return;
    }
    else {
        int i = vec[id].second;
        int tm = (tl + tr)/2;
        if (i <= tm) {
            upd(id, er, 2*n, tl, tm);
        }
        else {
            upd(id, er, 2*n+1, tm+1, tr);
        }
    }
}
pair<int, int> query(int l, int r, int higher, int n = 1, int tl = 0, int tr = MAXQ-1) {
    if (l > tr || r < tl) {
        return {MAXN, -1};
    }
    else if (l <= tl && tr <= r) {
        auto res = mn[n].upper_bound({higher, -1});
        if (res==mn[n].end()) {
            return {MAXN, -1};
        }
        return *res;
    }
    else {
        int tm = (tl + tr)/2;
        return min(query(l, r, higher, 2*n, tl, tm), query(l, r, higher, 2*n+1, tm+1, tr));
    }
}
void init(int n, int A[], int B[]) {
    N = n;
    vec.resize(N);
    for (int i = 0; i < N; i++) {
        vec[i] = {B[i], A[i]};
        upd(i, false);
    }
}

int can(int M, int K[]) {
    vector<int> k(M);
    for (int i = 0; i < M; i++) {
        k[i] = K[i];
    }
    sort(all(k));
    vector<int> remd;
    for (int a : k) {
        int temp = a;
        while (temp-->0) {
            auto next = query(0, a, a);
            if (next.second == -1) {
                for (int i : remd) {
                    upd(i, false);
                }
                return 0;
            }
            else {
                upd(next.second, true);
                remd.push_back(next.second);
            }
        }
    }
    for (int i : remd) {
        upd(i, false);
    }
    return 1;
}

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