Submission #990232

#	Time	Username	Problem	Language	Result	Execution time	Memory
990232		AdamGS	Teams (IOI15_teams)	C++17	100 / 100	3632 ms	364636 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct item * pitem;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item {
  pitem l=nullptr, r=nullptr;
  int x=0;
};
const int LIM=5e5+7;
pitem roots[LIM];
pair<int,int>T[LIM];
int n, N=1;
void build(pitem v, int l, int r) {
  if(l==r) return;
  v->l=new item();
  v->r=new item();
  int mid=(l+r)/2;
  build(v->l, l, mid);
  build(v->r, mid+1, r);
}
pitem upd(pitem v, int l, int r, int a) {
  if(r<a || a<l) return v;
  pitem x=new item();
  x->x=v->x+1;
  if(l==r) {
    x->l=v->r;
    x->r=v->r;
    return x;
  }
  int mid=(l+r)/2;
  x->l=upd(v->l, l, mid, a);
  x->r=upd(v->r, mid+1, r, a);
  x->x=x->l->x+x->r->x;
  return x;
}
int cnt(pitem v, int l, int r, int a, int b) {
  if(r<a || b<l) return 0;
  if(a<=l && r<=b) return v->x;
  int mid=(l+r)/2;
  return cnt(v->l, l, mid, a, b)+cnt(v->r, mid+1, r, a, b);
}
int kwad(int l, int r, int a, int b) {
  return cnt(roots[r+1], 0, N-1, a, b)-cnt(roots[l], 0, N-1, a, b);
}
void init(int _N, int A[], int B[]) {
  n=_N;
  while(N<=n) N*=2;
  rep(i, n) T[i]={B[i], A[i]};
  sort(T, T+n);
  T[n]={n+1, 0};
  roots[0]=new item();
  build(roots[0], 0, N-1);
  rep(i, n+1) roots[i+1]=upd(roots[i], 0, N-1, T[i].nd);
}
int znajdz(int x) {
  int po=0, ko=n;
  while(po<ko) {
    int sr=(po+ko)/2;
    if(T[sr].st<x) po=sr+1; else ko=sr;
  }
  return po;
}
int can(int m, int K[]) {
  sort(K, K+m);
  int sum=0;
  rep(i, m) {
    sum+=K[i];
    if(sum>n) return 0;
  }
  vector<pair<int,int>>P;
  P.pb({0, n});
  vector<pair<int,int>>Q;
  Q.pb({K[0], K[0]});
  for(int i=1; i<m; ++i) if(K[i]!=Q.back().st) Q.pb({K[i], K[i]}); else Q[Q.size()-1].nd+=K[i];
  m=Q.size();
  rep(i, m) {
    int x=Q[i].nd, a=znajdz(Q[i].st);
    if(a==n) return 0;
    while(P.back().nd<a) P.pop_back();
    while(P.size()>0) {
      int c=kwad(a, P.back().nd, P.back().st+1, Q[i].st);
      if(c>=x) break;
      x-=c;
      a=P.back().nd+1;
      P.pop_back();
    }
    if(P.size()==0) return 0;
    int po=a, ko=n;
    int o=cnt(roots[a], 0, N-1, P.back().st+1, Q[i].st);
    while(po<ko) {
      int sr=(po+ko)/2;
      if(cnt(roots[sr+1], 0, N-1, P.back().st+1, Q[i].st)-o<x) po=sr+1; else ko=sr;
    }
    P.pb({Q[i].st, po});
  }
  return 1;
}

Compilation message (stderr)

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

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