Submission #67854

#	Time	Username	Problem	Language	Result	Execution time	Memory
67854		funcsr	Teams (IOI15_teams)	C++17	0 / 100	4062 ms	525312 KiB

teams

#include "teams.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
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 MAX_N (1<<19)
struct Node {
  int val = 0;
  Node *left = NULL, *right = NULL;

  inline int value(Node *x) { return x==NULL?0:x->val; }

  int query(int a, int b, int k=0, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return val;
    int ret = 0;
    if (left)  ret += left->query(a, b, k*2+1, l, (l+r)/2);
    if (right) ret += right->query(a, b, k*2+2, (l+r)/2, r);
    return ret;
  }
  Node *add(int x, int v, int k=0, int l=0, int r=MAX_N) {
    if (r-l == 1) {
      assert(x == l);
      Node *ret = new Node();
      ret->val = val+v;
      return ret;
    }
    if (left == NULL) left = new Node();
    if (right == NULL) right = new Node();
    Node *ret = new Node();
    if (l <= x && x < (l+r)/2) {
      ret->left = left->add(x, v, k*2+1, l, (l+r)/2);
      ret->right = right;
    }
    else {
      ret->left = left;
      ret->right = right->add(x, v, k*2+2, (l+r)/2, r);
    }
    ret->val = value(ret->left) + value(ret->right);
    return ret;
  }
};

int N;
vector<int> Gopen[500001];
vector<int> Gclose[500001];
Node *seg[500001];

inline int count(int l, int a, int b) { return seg[l]->query(a, b+1); }

void init(int NN, int A[], int B[]) {
  N = NN;
  rep(i, N) {
    Gopen[A[i]].pb(B[i]);
    Gclose[B[i]+1].pb(B[i]);
  }
  seg[0] = new Node();
  rep(i, N+1) {
    for (int r : Gopen[i]) seg[i] = seg[i]->add(r, +1);
    for (int r : Gclose[i]) seg[i] = seg[i]->add(r, -1);
    if (i+1 <= N) seg[i+1] = seg[i];
  }
}

int can(int M, int K[]) {
  long long sum = 0;
  rep(i, M) sum += K[i];
  if (sum > N) return 0;
  sort(K, K+M);
  vector<int> xs(K, K+M); uniq(xs);
  vector<int> C(xs.size(), 0);
  vector<int> demand(xs.size(), 0);
  rep(i, M) demand[index(xs, K[i])]+=K[i];

  rep(k, xs.size()) {
    int lpos = k==0?0:(xs[k-1]+1);
    for (int r=k; r<xs.size(); r++) {
      int rpos = k+1==xs.size()?N:(xs[k+1]-1);
      C[r] += count(xs[k], xs[k], rpos) - (lpos>=1?count(lpos-1, xs[k], rpos):0);
    }
    for (int r=k; r<xs.size(); r++) {
      int e = min(demand[k], C[r]);
      demand[k] -= e;
      C[r] -= e;
    }
    if (demand[k] > 0) return 0;
  }
  return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
teams.cpp:82:3: note: in expansion of macro 'rep'
   rep(k, xs.size()) {
   ^~~
teams.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int r=k; r<xs.size(); r++) {
                   ~^~~~~~~~~~
teams.cpp:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       int rpos = k+1==xs.size()?N:(xs[k+1]-1);
                  ~~~^~~~~~~~~~~
teams.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int r=k; r<xs.size(); r++) {
                   ~^~~~~~~~~~

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