Submission #597522

#	Time	Username	Problem	Language	Result	Execution time	Memory
597522		AlexLuchianov	Teams (IOI15_teams)	C++14	100 / 100	2211 ms	492672 KiB

teams

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

int const nmax = 5000000;
std::pair<int,int> v[5 + nmax];
std::vector<int> frec[5 + nmax];

namespace PST{
  struct Node{
    int result;
    Node* left;
    Node* right;
    Node(int val = 0) {
      result = val;
      left = right = nullptr;
    }
    void refresh() {
      this->result = this->left->result + this->right->result;
    }
  };
  
  Node* build(int from, int to) {
    Node *node = new Node(0);
    if(from < to) {
      int mid = (from + to) / 2;
      node->left = build(from, mid);
      node->right = build(mid + 1, to);
    }
    return node;
  }
  
  Node* initialize(int n) {
    return build(1, n);   
  }


  Node* update(Node* base, int from, int to, int x, int val) {
    if(from < to) {
      int mid = (from + to) / 2;
      Node* newNode = new Node();
      (*newNode) = (*base);
      if(x <= mid)
        newNode->left = update(base->left, from, mid, x, val);
      else
        newNode->right = update(base->right, mid + 1, to, x, val);
      newNode->refresh();
      return newNode;
    } else
      return (new Node(val));
  }

  int query(Node* node, int from, int to, int x, int y) {
    assert(from <= x && x <= y && y <= to);
    if(from == x && to == y)
      return node->result;
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node->left, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node->right, mid + 1, to, x, y);
      else
        return query(node->left, from, mid,x , mid) + 
               query(node->right, mid + 1, to, mid + 1, y);
    }
  }
  
  Node* version[5 + nmax];
  int n;

  void buildVersions(int n_) {
    n = n_;
    Node* part = initialize(n);
    for(int i = 0; i <= n; i++) {
      for(auto pos : frec[i]) {
        part = update(part, 0,  n - 1, pos, 1);
      }
      version[i] = part;
    }
  }
  
  int KthElement(int from, int to, int k) {
    int x = 0;
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(x + jump <= n && query(version[x + jump], 0, n - 1, from, to) < k)
        x += jump;
    return x + 1;
  }
};

int n;
void init(int N, int A[], int B[]) {
  n = N;
  for(int i = 0; i < n; i++) {
    v[i].first = A[i];
    v[i].second = B[i];
  }
  std::sort(v, v + n);
  for(int i = 0; i < n; i++)
    frec[v[i].second].push_back(i);
  PST::buildVersions(n);
}

struct Interval{
  int x;
  int y;
  int pos;
};

int can(int M, int K[]) {
	std::vector<int> queries(M);
  for(int i = 0; i < M; i++)
    queries[i] = K[i];
  std::sort(queries.begin(), queries.end());
  int ptr = 0;
  std::vector<Interval> st;
  for(int i = 0; i < M; i++) {
    int newPtr = ptr;
    for(int jump = (1 << 20); 0 < jump; jump /= 2)
      if(newPtr + jump <= n && v[newPtr + jump - 1].first <= queries[i])
        newPtr += jump;
    if(ptr < newPtr)
      st.push_back({ptr, newPtr - 1, 0});
    ptr = newPtr;
    int acc = queries[i];
    while(0 < acc) {
      if(1 == st.size()) {
        st[0].pos = std::max(st[0].pos, PST::query(PST::version[queries[i] - 1], 0, n - 1, st[0].x, st[0].y));
        if(st[0].pos + acc <= (st[0].y - st[0].x + 1)) {
          st[0].pos += acc;
          acc = 0;
          break;
        } else
          return 0;
      } else {
        int stSize = st.size();
        st[stSize - 1].pos = std::max(st[stSize - 1].pos, PST::query(PST::version[queries[i] - 1], 0, n - 1, st[stSize - 1].x, st[stSize - 1].y));
        st[stSize - 2].pos = std::max(st[stSize - 2].pos, PST::query(PST::version[queries[i] - 1], 0, n - 1, st[stSize - 2].x, st[stSize - 2].y));
        int val = PST::KthElement(st[stSize - 2].x, st[stSize - 2].y, st[stSize - 2].pos);
        int newElements = std::max(0, PST::query(PST::version[val - 1], 0, n - 1, st[stSize - 1].x, st[stSize - 1].y) - st[stSize - 1].pos);
        if(newElements <= acc) {
          st[stSize - 2].pos += st[stSize - 1].pos + newElements;
          st[stSize - 2].y = st[stSize - 1].y;
          st.pop_back();
          acc -= newElements;
        } else {
          st[stSize - 1].pos += acc;
          acc = 0;
        }
      }
    }
  }
  return 1;
}

Compilation message (stderr)

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

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