Submission #955083

#	Time	Username	Problem	Language	Result	Execution time	Memory
955083		kunzaZa183	Teams (IOI15_teams)	C++17	0 / 100	310 ms	70636 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000;

pair<int, int> arrpii[maxn];

int n, order[maxn], last[maxn], where[maxn];

struct node
{
  int val, ct;
  node *l, *r;
  node()
  {
    val = INT_MAX, ct = 0;
    l = NULL, r = NULL;
  }
} *allseg[maxn];

void build(node *sth, int curl, int curr)
{
  if (curl == curr)
    return;
  sth->l = new node, sth->r = new node;
  build(sth->l, curl, (curl + curr) / 2);
  build(sth->r, (curl + curr) / 2 + 1, curr);
}

node *update(node *old, int curl, int curr, int in, int val)
{
  node *tmp = new node;
  if (curl == curr)
  {
    tmp->val = val;
    tmp->ct = 1;
    return tmp;
  }
  int mid = (curl + curr) / 2;
  if (in <= mid)
  {
    tmp->l = update(old->l, curl, mid, in, val);
    tmp->r = old->r;
  }
  else
  {
    tmp->l = old->l;
    tmp->r = update(old->r, mid + 1, curr, in, val);
  }
  tmp->ct = tmp->l->ct + tmp->r->ct;
  tmp->val = min(tmp->l->val, tmp->r->val);
  return tmp;
}

void init(int N, int A[], int B[])
{
  n = N;
  for (int i = 0; i < N; i++)
    arrpii[i] = {A[i], B[i]};
  sort(arrpii, arrpii + N, [](pair<int, int> a, pair<int, int> b)
       { return a.second < b.second; });
  for (int i = 0; i < n; i++)
    order[i] = i;
  sort(order, order + n, [](int a, int b)
       { return arrpii[a] > arrpii[b]; });
  for (int i = 0; i < n; i++)
    where[order[i]] = i;
  allseg[0] = new node;
  build(allseg[0], 0, n - 1);
  for (int i = 0; i < n; i++)
    allseg[i + 1] = update(allseg[i], 0, n - 1, where[i], arrpii[i].first);
}

int query(node *curl, node *curr, int val)
{
  if (curr->ct - curl->ct < val)
    return -1;
  if (curl->l == NULL)
    return curr->val;
  if (curr->l->ct - curl->l->ct >= val)
    return query(curl->l, curr->l, val);
  return query(curl->r, curr->r, val - (curr->l->ct - curl->l->ct));
}

int howmany(node *cur, int curl, int curr, int ranger, int rangel)
{
  if (rangel > arrpii[order[curl]].first || arrpii[order[curr]].first > ranger)
    return 0;
  if (ranger >= arrpii[order[curl]].first && arrpii[order[curr]].first >= rangel)
    return cur->ct;
  return howmany(cur->l, curl, (curl + curr) / 2, ranger, rangel) + howmany(cur->r, (curl + curr) / 2 + 1, curr, ranger, rangel);
}

int can(int M, int K[])
{
  sort(K, K + M, greater<int>());
  int extra = 0, furthest = INT_MAX;
  for (int i = 0; i < M; i++)
  {
    int pos = lower_bound(arrpii, arrpii + n, make_pair(INT_MIN, K[i]), [](pair<int, int> a, pair<int, int> b)
                          { return a.second < b.second; }) -
              arrpii;
    if (pos == n)
      return 0;
    if (K[i] < furthest)
    {
      furthest = K[i];
      extra = 0;
    }
    node *bef = allseg[pos], *all = allseg[n];
    int ctbef = howmany(all, 0, n - 1, INT_MAX, furthest + 1) - howmany(bef, 0, n - 1, INT_MAX, furthest + 1);
    int needto = K[i] + extra + ctbef;
    int k = query(bef, all, needto);
    furthest = min(furthest, k);
    if (k == -1)
      return 0;
    extra = needto - (howmany(all, 0, n - 1, INT_MAX, k + 1) - howmany(bef, 0, n - 1, INT_MAX, k + 1));
  }
  return 1;
}

// int main()
// {
//   freopen("in.txt", "r", stdin);
//   freopen("out.txt", "w", stdout);
//   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] >> 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];
//     }
//     cout << can(M, K) << '\n';
//   }
//   return 0;
// }

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:102:60: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  101 |     int pos = lower_bound(arrpii, arrpii + n, make_pair(INT_MIN, K[i]), [](pair<int, int> a, pair<int, int> b)
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  102 |                           { return a.second < b.second; }) -
      |                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
  103 |               arrpii;
      |               ~~~~~~

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