Submission #588489

#	Time	Username	Problem	Language	Result	Execution time	Memory
588489		lorenzoferrari	Teams (IOI15_teams)	C++17	0 / 100	3253 ms	55508 KiB

teams

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

int n;
vector<vector<int>> ft;

int count(const vector<vector<int>*>& v, int l, int r) {
  // return elements in [l, r]
  if (l > r) return 0;
  int ans = 0;
  for (auto p : v) {
    ans += upper_bound(p->begin(), p->end(), r) -
           upper_bound(p->begin(), p->end(), l-1);
  }
  return ans;
}

vector<vector<int>*> get_prefix(int a) {
  vector<vector<int>*> ans;
  for (; a > 0; a -= (a & -a)) {
    ans.push_back(&ft[a]);
  }
  return ans;
}

int can(int M, int K[]) {
// cerr << "query: \n";
  sort(K, K + M);
  int delta = 0;
  for (int i = 0; i < M; ++i) {
    auto p = get_prefix(K[i]);
//     for (auto x : p) for (auto y : *x) cerr << y << " ";
//     cerr << endl;
    int l = K[i]-1, r = n;
    while (r - l > 1) {
      int m = (l + r) / 2;
      if (count(p, K[i], m) >= K[i] + delta) {
        r = m;
      } else {
        l = m;
      }
    }
    if (count(p, K[i], r) < K[i] + delta) return 0;
    if (i != M-1) {
      if (K[i+1] > r) {
        delta = 0;
      } else {
        int r_used = K[i] + delta - count(p, K[i], r-1);
        delta = count(p, K[i+1], r-1) + r_used;
      }
    }
  }
  return 1;
}

void init(int n, int a[], int b[]) {
  ::n = n;
  ft.resize(n + 1);
  for (int i = 0; i < n; ++i) {
    for (int j = a[i]; j <= n; j += (j & -j)) {
      ft[j].push_back(b[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    sort(ft[i].begin(), ft[i].end());
  }
}

Compilation message (stderr)

teams.cpp: In function 'int count(const std::vector<std::vector<int>*>&, int, int)':
teams.cpp:14:49: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   14 |            upper_bound(p->begin(), p->end(), l-1);
      |                                                 ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:57:15: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   57 | void init(int n, int a[], int b[]) {
      |           ~~~~^
teams.cpp:5:5: note: shadowed declaration is here
    5 | int n;
      |     ^

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