Submission #726907

#	Time	Username	Problem	Language	Result	Execution time	Memory
726907		Alex_tz307	Teams (IOI15_teams)	C++17	100 / 100	2683 ms	383000 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

struct node {
  int sum;
  node* l;
  node* r;

  node() : sum(0), l(nullptr), r(nullptr) {}
};

const int kN = 5e5;
int n, ver[1 + kN], used[kN];
node *roots[1 + kN];
vector<int> rEnd[1 + kN];
vector<pair<int, int>> intervals;

void build(node *root, int lx, int rx) {
  if (lx == rx) {
    return;
  }

  int mid = (lx + rx) / 2;

  root->l = new node;
  build(root->l, lx, mid);

  root->r = new node;
  build(root->r, mid + 1, rx);
}

void update(node *prev, node *curr, int lx, int rx, int pos) {
  if (lx == rx) {
    curr->sum = prev->sum + 1;
    return;
  }

  int mid = (lx + rx) / 2;

  if (pos <= mid) {
    curr->l = new node;
    curr->r = prev->r;
    update(prev->l, curr->l, lx, mid, pos);
  } else {
    curr->l = prev->l;
    curr->r = new node;
    update(prev->r, curr->r, mid + 1, rx, pos);
  }

  curr->sum = curr->l->sum + curr->r->sum;
}

int query(node *root, int lx, int rx, int st, int dr) {
  if (st <= lx && rx <= dr) {
    return root->sum;
  }

  int mid = (lx + rx) / 2;

  int sum = 0;

  if (st <= mid) {
    sum += query(root->l, lx, mid, st, dr);
  }

  if (mid < dr) {
    sum += query(root->r, mid + 1, rx, st, dr);
  }

  return sum;
}

void init(int N, int A[], int B[]) {
  n = N;

  for (int i = 0; i < N; ++i) {
    rEnd[A[i]].emplace_back(B[i]);
  }

  roots[0] = new node;
  build(roots[0], 1, n);

  int version = 0;

  for (int l = 1; l <= n; ++l) {
    for (const int &r : rEnd[l]) {
      version += 1;
      roots[version] = new node;
      update(roots[version - 1], roots[version], 1, n, r);
    }

    ver[l] = version;
  }
}

int can(int m, int a[]) {
  int sum = 0;

  for (int i = 0; i < m; ++i) {
    sum += a[i];

    if (n < sum) {
      return 0;
    }
  }

  sort(a, a + m);

  intervals.clear();

  int last = a[0];

  for (int i = 1; i < m; ++i) {
    if (last != a[i]) {
      intervals.emplace_back(last, a[i] - 1);
    }
    last = a[i];
  }

  intervals.emplace_back(last, n);

  int R = intervals.size();

  for (int i = 0; i < R; ++i) {
    used[i] = 0;
  }

  int ptr = 0;

  for (int i = 0; i < m; ++i) {
    int j = i;

    while (j < m && a[i] == a[j]) {
      j += 1;
    }

    int req = a[i] * (j - i);

    for (int k = ptr; k < R && req; ++k) {
      int l, r;
      tie(l, r) = intervals[k];

      int take = min(req, query(roots[ver[a[i]]], 1, n, l, r) - used[k]);

      req -= take;

      used[k] += take;
    }

    if (req) {
      return 0;
    }

    i = j - 1;
    ptr += 1;
  }

  return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:124:25: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  124 |   int R = intervals.size();
      |           ~~~~~~~~~~~~~~^~

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