Submission #770798

#	Time	Username	Problem	Language	Result	Execution time	Memory
770798		That_Salamander	Teams (IOI15_teams)	C++14	34 / 100	4067 ms	38572 KiB

teams

#include <bits/stdc++.h>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int n, a[500000], b[500000];

void init(int N, int A[], int B[]) {
    n = N;
    memcpy(a, A, n * sizeof(a[0]));
    memcpy(b, B, n * sizeof(b[0]));
}

int can(int m, int k[]) {
    sort(k, k + m);

    auto cmp = [](pii a, pii b) {
        return pii{a.second, a.first} < pii{b.second, b.first};
    };

    multiset<pair<int, int>> unused;
    multiset<pair<int, int>, decltype(cmp)> available(cmp);

    FOR(i, n) {
        unused.insert({a[i], b[i]});
    }

    FOR(i, m) {
        int v = k[i];

        while (unused.size() && unused.begin()->first <= v) {
            available.insert(*(unused.begin()));
            unused.erase(unused.begin());
        }

        while (available.size() && available.begin() ->second < v) {
            available.erase(available.begin());
        }

        FOR(j, v) {
            if (available.empty()) return 0;
            available.erase(available.begin());
        }
    }

    return true;
}

#ifdef LOCAL_TEST
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> a(n), b(n);

    FOR(i, n) {
        cin >> a[i] >> b[i];
    }

    init(n, a.data(), b.data());

    int q;
    cin >> q;

    FOR(i, q) {
        int m;
        cin >> m;

        vector<int> k(m);

        FOR(j, m) {
            cin >> k[j];
        }

        cout << (can(m, k.data()) ? "YES" : "NO") << endl;
    }
}
#endif

Compilation message (stderr)

teams.cpp: In lambda function:
teams.cpp:25:30: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   25 |     auto cmp = [](pii a, pii b) {
      |                          ~~~~^
teams.cpp:14:19: note: shadowed declaration is here
   14 | int n, a[500000], b[500000];
      |                   ^
teams.cpp:25:23: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   25 |     auto cmp = [](pii a, pii b) {
      |                   ~~~~^
teams.cpp:14:8: note: shadowed declaration is here
   14 | int n, a[500000], b[500000];
      |        ^

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