Submission #173119

#	Time	Username	Problem	Language	Result	Execution time	Memory
173119		AlexLuchianov	Teams (IOI15_teams)	C++14	34 / 100	1259 ms	524288 KiB

teams

#include "teams.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 500000;
struct Child{
  int x;
  int y;
  bool operator < (Child const &a) const{
    return x < a.x;
  }
} v[1 + nmax];
int jumpsize[1 + nmax];

class SegmentTree{
private:
  int n;
  std::vector<std::vector<int>> aint;
  std::vector<std::vector<int>> leftedge, rightedge;
public:
  SegmentTree(int n = 0){
    this->n = n;
    aint.resize(4 * n);
    leftedge.resize(4 * n);
    rightedge.resize(4 * n);
  }
  void build(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
      aint[node].push_back(0);
      aint[node].resize(to - from + 2);
      merge(aint[node * 2].begin() + 1, aint[node * 2].end(), aint[node * 2 + 1].begin() + 1, aint[node * 2 + 1].end(), aint[node].begin() + 1);

      leftedge[node].resize(to - from + 2);
      rightedge[node].resize(to - from + 2);

      //std::cout << ":";
      int ptr = 0;

      //std::cout << leftedge[node].size() << " " <<  aint[node].size() << '\n';
      for(int i = 0; i < leftedge[node].size(); i++){
        while(ptr + 1 < aint[node * 2].size() && aint[node * 2][ptr + 1] <= aint[node][i])
          ptr++;
        leftedge[node][i] = ptr;
      }
      //std::cout << "*";
      ptr = 0;
      for(int i = 0; i < rightedge[node].size(); i++){
        while(ptr + 1 < aint[node * 2 + 1].size() && aint[node * 2 + 1][ptr + 1] <= aint[node][i])
          ptr++;
        rightedge[node][i] = ptr;
      }
      //std::cout << "|";
    } else {
      aint[node].push_back(0);
      aint[node].push_back(v[from].y);
    }
    /*
    std::cout << node << " " << from << " " << to << '\n';
    for(int i = 0; i < aint[node].size(); i++)
      std::cout << aint[node][i] << " ";
    std::cout << '\n';
    for(int i = 0; i < leftedge[node].size(); i++)
      std::cout << leftedge[node][i] << " ";
    std::cout << '\n';
    for(int i = 0; i < rightedge[node].size(); i++)
      std::cout << rightedge[node][i] << " ";
    std::cout << '\n' << '\n';
    //*/
  }
  ///counts how many values are lower(or equal) than target in node

  int lowerthan(int node, int target){
    if(aint[node].size() == 0)
      return 0;
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(x + jump < aint[node].size() && aint[node][x + jump] <= target)
        x += jump;
    return x;
  }

  int query(int node, int from, int to, int x, int y, int pos){
    if(y < x)
      return 0;
    if(from == x && to == y)
      return pos;
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y, leftedge[node][pos]);
      else if(x <= mid && mid + 1 <= y)
        return query(node * 2, from, mid, x, mid, leftedge[node][pos]) + query(node * 2 + 1, mid + 1, to, mid + 1, y, rightedge[node][pos]);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y, rightedge[node][pos]);
      else{
        ///Something is definitely wrong
        assert(1 < 0);
        return 0;
      }
    }
  }
};

int N;
SegmentTree aint;

int pos[1 + nmax];

void init(int N_, int A[], int B[]) {
  N = N_;
  jumpsize[1] = 1;
  for(int i = 2;i <= N; i++)
    jumpsize[i] = jumpsize[i / 2] * 2;

  for(int i = 1;i <= N; i++)
    v[i] = {A[i - 1], B[i - 1]};
  std::sort(v + 1, v + N + 1);
  int ptr = 0;
  for(int i = 1;i <= N; i++){
    while(ptr < N && v[ptr + 1].x <= i)
      ptr++;
    pos[i] = ptr;
  }
  aint = SegmentTree(N);
  aint.build(1, 1, N);

}

int cost[1 + nmax];
int pocket[1 + nmax];

int elapse = 0;

int can(int M, int K[]) {
  elapse++;
  if(2 == elapse && 90000 <= N)
    assert(1 < 0);

  int sum = 0;
  for(int i = 0; i < M; i++)
    sum += K[i];
  if(N < sum)
    return 0;
  std::vector<int> candidates;
  candidates.push_back(0);
  candidates.push_back(N + 1);
  for(int i = 0; i < M; i++){
    candidates.push_back(K[i]);
    cost[K[i]] += K[i];
  }
  std::sort(candidates.begin(), candidates.end());
  candidates.erase(unique(candidates.begin(), candidates.end()) , candidates.end());

  for(int i = 1; i < candidates.size() - 1; i++){
    int last = pos[candidates[i - 1]];
    int curr = pos[candidates[i]];

    int lastsum = aint.query(1, 1, N, last + 1, curr, aint.lowerthan(1, candidates[i] - 1));
    for(int j = i;j < candidates.size() - 1; j++){
      int sum = aint.query(1, 1, N, last + 1, curr, aint.lowerthan(1, candidates[j + 1] - 1));
      pocket[candidates[j]] += sum - lastsum;
      lastsum = sum;
    }

    for(int j = i; j < candidates.size(); j++){
      if(0 < cost[candidates[i]] && 0 < pocket[candidates[j]]){
        int val = MIN(cost[candidates[i]], pocket[candidates[j]]);
        cost[candidates[i]] -= val;
        pocket[candidates[j]] -= val;
      }
    }
    if(0 < cost[candidates[i]]){
      for(int i = 0; i < M; i++) {
        cost[K[i]] = 0;
        pocket[K[i]] = 0;
      }
      return 0;
    }
  }

  for(int i = 0; i < M; i++) {
    cost[K[i]] = 0;
    pocket[K[i]] = 0;
  }
  return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'SegmentTree::SegmentTree(int)':
teams.cpp:27:25: warning: declaration of 'n' shadows a member of 'SegmentTree' [-Wshadow]
   SegmentTree(int n = 0){
                         ^
teams.cpp:23:7: note: shadowed declaration is here
   int n;
       ^
teams.cpp: In member function 'void SegmentTree::build(int, int, int)':
teams.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < leftedge[node].size(); i++){
                      ~~^~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:50:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ptr + 1 < aint[node * 2].size() && aint[node * 2][ptr + 1] <= aint[node][i])
               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < rightedge[node].size(); i++){
                      ~~^~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ptr + 1 < aint[node * 2 + 1].size() && aint[node * 2 + 1][ptr + 1] <= aint[node][i])
               ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'int SegmentTree::lowerthan(int, int)':
teams.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(x + jump < aint[node].size() && aint[node][x + jump] <= target)
          ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:163:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < candidates.size() - 1; i++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:168:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = i;j < candidates.size() - 1; j++){
                   ~~^~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:169:11: warning: declaration of 'sum' shadows a previous local [-Wshadow]
       int sum = aint.query(1, 1, N, last + 1, curr, aint.lowerthan(1, candidates[j + 1] - 1));
           ^~~
teams.cpp:148:7: note: shadowed declaration is here
   int sum = 0;
       ^~~
teams.cpp:174:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = i; j < candidates.size(); j++){
                    ~~^~~~~~~~~~~~~~~~~~~
teams.cpp:182:15: warning: declaration of 'i' shadows a previous local [-Wshadow]
       for(int i = 0; i < M; i++) {
               ^
teams.cpp:163:11: note: shadowed declaration is here
   for(int i = 1; i < candidates.size() - 1; i++){
           ^

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