Submission #1121375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121375		epicci23	Teams (IOI15_teams)	C++17	77 / 100	4075 ms	366780 KiB

teams

#include "bits/stdc++.h"
#include "teams.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int BL = 350;
const int N = 5e5 + 5;

struct Node{
  Node* lc;
  Node* rc;
  int sum;
  Node(){
  	lc = rc = NULL;
  	sum = 0;
  }
};

vector<Node*> seg;
vector<array<int,2>> v;
int n;


Node* build(int l,int r){
  if(l == r) return new Node();
  int m = (l + r) / 2;
  Node* res = new Node();
  res -> lc = build(l, m);
  res -> rc = build(m + 1, r);
  return res;
}

Node* upd(Node* rt,int l,int r,int ind){
  if(l == r){
  	Node* res = new Node();
  	res -> sum = rt -> sum + 1;
  	return res;
  }
  Node* res = new Node();
  int m = (l + r) / 2;
  if(ind <= m){
  	res -> lc = upd(rt -> lc, l, m, ind);
  	res -> rc = rt -> rc; 
  }
  else{
  	res -> lc = rt -> lc;
  	res -> rc = upd(rt -> rc, m + 1, r, ind); 
  }
  res -> sum = res -> lc -> sum + res -> rc -> sum;
  return res;
}

int query(Node* rt,int l,int r,int gl,int gr){
  if(r < gl || l > gr) return 0;
  if(l >= gl && r <= gr) return rt -> sum;
  int m = (l + r) / 2;
  return query(rt -> lc, l, m,gl,gr) + query(rt -> rc,m + 1, r, gl, gr);
}

void init(int _n, int A[], int B[]){
  n = _n;
  for(int i = 0 ; i < n ; i++) v.push_back({A[i], B[i]});
  sort(all(v));
  seg.push_back(build(1,N));
  for(int i = 0 ; i < n ; i++) seg.push_back(upd(seg.back(),1,N,v[i][1]));
}

int Get_Sum(int l,int r){
  int it = upper_bound(all(v),array<int,2>{l+1,-1}) - v.begin();
  return query(seg[it],1,N,r,N);
}

int can(int M, int K[]){
 sort(K,K+M);

 if(M >= BL){
  int p = 0;
  priority_queue<int,vector<int>,greater<int>> pq;
  for(int i = 0 ; i < M ; i++){
  	int val = K[i];
    while(p < n && v[p][0] <= val) pq.push(v[p++][1]);
    while(!pq.empty() && pq.top() < val) pq.pop();
    if(sz(pq) < val) return 0;
    while(val--) pq.pop();
  }
  return 1;
 }

 int dp[M];  
 for(int i = 0; i < M; i++){
   dp[i] = Get_Sum(K[i], K[i]) - K[i];
   for(int j = i - 1 ; j >= 0 ; j--){
   	dp[i] = min(dp[i], dp[j] - K[i] + Get_Sum(K[i], K[i]) - Get_Sum(K[j], K[i]));
   }
   if(dp[i] < 0) return 0;
 }

 return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int Get_Sum(int, int)':
teams.cpp:70:53: warning: conversion from '__gnu_cxx::__normal_iterator<std::array<int, 2>*, std::vector<std::array<int, 2> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   70 |   int it = upper_bound(all(v),array<int,2>{l+1,-1}) - v.begin();
      |            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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