Submission #402333

#	Time	Username	Problem	Language	Result	Execution time	Memory
402333		oolimry	Teams (IOI15_teams)	C++17	100 / 100	1683 ms	101076 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<int, int> ii;

///segment tree begin
const int N = 1 << 19;
vector<int> tree[2*N];
inline void update(int a, int b){
	for(b += N;b > 0;b >>= 1) tree[b].push_back(a);
}
inline void getready(){
	for(int i = 0;i < 2*N;i++) sort(all(tree[i]));
}
inline int get(int u, int a, int A){
	return upper_bound(all(tree[u]), A) - lower_bound(all(tree[u]), a);
}
inline int querypos(int a, int A, int need){
	int u = 1;
	for(int i = 1;i <= 19;i++){
		int lc = u<<1; int rc = lc+1;
		int G = get(rc,a,A);
		if(need > G){
			need -= G;
			u = lc;
		}
		else u = rc;
	}
	return u-N;
}
inline int query(int a, int A, int l, int r){
	int res = 0;
	for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res += get(l++,a,A);
		if(r&1) res += get(--r,a,A);
	}
	return res;
}
///segment tree end

int cross[500005];
void init(int n, int A[], int B[]) {
	for(int i = 0;i < n;i++) update(A[i], B[i]);
	getready();
	for(int i = 0;i < n;i++) cross[A[i]]++, cross[B[i]+1]--;
	for(int i = 1;i <= 500000;i++) cross[i] += cross[i-1];
}

map<int,int> best;
priority_queue<ii, vector<ii>, greater<ii> > pq;

void create(int i){
	auto b = best.find(i);
	assert(b != best.begin() and b != best.end());
	auto a = prev(b);
	int diff = b->second - a->second;
	
	
	int C = querypos(a->first+1, b->first, diff) + 1;
	pq.push(ii(C,b->first));
}

void insert(int i, int dp){
	if(best.empty()){
		best[i] = dp;
		return;
	}
	best[i] = dp;
	create(i);
}

void process(int limit){
	while(!pq.empty()){
		ii T = pq.top(); 
		if(T.first > limit) break;
		pq.pop();
		
		int i = T.second;
		auto it = best.find(i);
		if(it == best.end()) continue;
		
		auto nxtit = next(it);
		int nxt = -1;
		if(nxtit != best.end()) nxt = nxtit->first;
		
		best.erase(it);
		if(nxt != -1) create(nxt);
	}
}

int can(int M, int K[]) {
	best.clear(); while(!pq.empty()) pq.pop();
	sort(K,K+M);
	
	long long total = 0;
	for(int i = 0;i < M;i++) total += K[i];
	if(total > 500000) return 0; ///idk why preemptive pruning
	
	int acc = 0;
	for(int i = 0;i < M;i++){
		acc += K[i];
		if(i != M-1 and K[i] == K[i+1]) continue; ///accumulate the queries
		
		process(K[i]);
				
		int dp = cross[K[i]]; ///dp = children - projects, if dp goes negative then return 0
		if(not best.empty()){
			auto it = best.end(); it--;
			dp = min(dp, it->second + query(it->first+1, K[i], K[i], N-1));
		}


		dp -= acc;
		if(dp < 0) return 0;
		
		insert(K[i], dp);		
		
		acc = 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int get(int, int, int)':
teams.cpp:22:38: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   22 |  return upper_bound(all(tree[u]), A) - lower_bound(all(tree[u]), a);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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