Submission #41708

#	Time	Username	Problem	Language	Result	Execution time	Memory
41708		funcsr	Teams (IOI15_teams)	C++14	34 / 100	4082 ms	99668 KiB

teams

#include "teams.h"
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
typedef pair<int, int> P;

int N;
int A[500000], B[500000];
vector<int> Gstart[500001], Gend[500001];
void init(int NN, int AA[], int BB[]) {
  N = NN;
  vector<P> ps;
  rep(i, N) ps.pb(P(BB[i], i));
  sort(all(ps));
  rep(i, N) A[i] = AA[ps[i]._2], B[i] = BB[ps[i]._2];
  rep(i, N) Gstart[A[i]].pb(i);
  rep(i, N) Gend[B[i]].pb(i);
}

int T[500001];
bool alive[500000];
int can(int M, int K[]) {
  rep(i, N) alive[i] = false;
  rep(i, N+1) T[i] = 0;
  rep(i, M) T[K[i]]++;
  priority_queue<int, vector<int>, greater<int> > q;
  rep(x, N+1) {
    for (int i : Gstart[x]) {
      alive[i] = true;
      q.push(i);
    }
    rep(times, T[x]) {
      rep(_, x) {
        while (!q.empty() && !alive[q.top()]) q.pop();
        if (q.empty()) return 0;
        alive[q.top()] = false;
        q.pop();
      }
    }
    for (int i : Gend[x]) alive[i] = false;
  }
  return 1;
}

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