Submission #1075897

#TimeUsernameProblemLanguageResultExecution timeMemory
1075897VictorTeams (IOI15_teams)C++17
34 / 100
4059 ms49972 KiB
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;

const ll INF = 1'000'000'007;


ll n;
vpll people;
void init(int N, int A[], int B[]) {
    n=N;
    rep(i,0,n) people.emplace_back(A[i],B[i]);
    sort(all(people));
}

int can(int M, int K[]) {
    sort(K,K+M);
    set<pll> order;
    ll j=0;
    rep(i,0,M) {
        while(j<n&&people[j].first<=K[i]) {
            order.emplace(people[j].second,j);
            ++j;
        }

        rep(k,0,K[i]) {
            while(sz(order)&&order.begin()->first<K[i]) order.erase(order.begin());
            if(!sz(order)) return 0;
            order.erase(order.begin());
        }
    }
    return 1;
}

/**
#include <stdio.h>
#include <stdlib.h>


static char buffer[1024];
static int currentChar = 0;
static int charsNumber = 0;

static inline int read() {
    if (charsNumber < 0) {
        exit(1);
    }
    if (!charsNumber || currentChar == charsNumber) {
        charsNumber = (int)fread(buffer, sizeof(buffer[0]), sizeof(buffer), stdin);
        currentChar = 0;
    }
    if (charsNumber <= 0) {
        return -1;
    }
    return buffer[currentChar++];
}

static inline int readInt() {
    int c, x, s;
    c = read();
    while (c <= 32)
        c = read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = read();
    }
    if (s < 0)
        x = -x;
    return x;
}

int main() {
    int N;
    cin>>N;
    int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
    int *B = (int *)malloc(sizeof(int) * (unsigned int)N);
    for (int i = 0; i < N; ++i) {
        cin>>A[i];
        cin>>B[i];
    }
    init(N, A, B);
    int Q;
    cin>>Q;
    for (int i = 0; i < Q; ++i) {
        int M;
        cin>>M;
        int *K = (int *)malloc(sizeof(int) * (unsigned int)M);
        for (int j = 0; j < M; ++j) {
            cin>>K[j];
        }
        fprintf(stdout, "%d\n", can(M, K));
    }
    fflush(stdout);
    _Exit(0);
    return 0;
}/**/

Compilation message (stderr)

teams.cpp:132:2: warning: "/*" within comment [-Wcomment]
  132 | }/**/
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...