Submission #284505

#	Time	Username	Problem	Language	Result	Execution time	Memory
284505		nvmdava	Teams (IOI15_teams)	C++17	100 / 100	1690 ms	383348 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second

const int N = 500005;

struct Node{
	int s;
	Node *L, *R;
	Node(int _s, Node *_L, Node *_R){
		s = _s; L = _L; R = _R;
	}
 
	int query(int l, int r, int le, int ri){
		if(le > r || ri < l) return 0;
		if(le <= l && r <= ri) return s;
		int m = (l + r) >> 1;
		return L -> query(l, m, le, ri) + R -> query(m + 1, r, le, ri);
	}
 
	Node* update(int l, int r, int x){
		if(l > x || r < x) return this;
		if(l == r) return new Node(s + 1, L, R);
		int m = (l + r) >> 1;
		return new Node(s + 1, L -> update(l, m, x), R -> update(m + 1, r, x));
	}
 
	void build(int l, int r){
		if(l == r) return;
		int m = (l + r) >> 1;
		L = new Node(0, NULL, NULL);
		R = new Node(0, NULL, NULL);
		L -> build(l, m);
		R -> build(m + 1, r);
	}
};
 
vector<int> lol[N];
 
Node* tree[N];
 
int query(int x1, int y1, int x2, int y2){
	--y1;
	return tree[y2] -> query(1, N, x1, x2) - tree[y1] -> query(1, N, x1, x2);
}
 
void init(int n, int A[], int B[]) {
	for(int i = 0; i < n; ++i)
		lol[B[i]].push_back(A[i]);
	tree[0] = new Node(0, NULL, NULL);
	tree[0] -> build(1, N);
	for(int i = 1; i < N; ++i){
		tree[i] = tree[i - 1];
		for(auto& x : lol[i]){
			tree[i] = tree[i] -> update(1, N, x);
		}
	}
}

vector<pair<int, int> > val;
vector<pair<int, pair<int, int> > > kil;

int can(int M, int K[]) {
	sort(K + 0, K + M);
	val.clear();
	for(int i = 0; i < M; ++i){
		if(val.empty() || val.back().ff != K[i])
			val.push_back({K[i], 0});
		val.back().ss += K[i];
		if(val.back().ss > N) return 0;
	}

	M = val.size();
	val.push_back({N, 0});
	kil = {{1, {M, 0}}};
	for(int i = 0; i < M; ++i){
		while(kil.back().ss.ff < i)
			kil.pop_back();
		while(kil.back().ss.ff == i){
			val[i].ss += kil.back().ss.ss;
			kil.pop_back();
			if(val[i].ss > N) return 0; 
		}
		int s, br = i;
		int sp = 0;
		while((s = query(kil.back().ff, val[br].ff, val[i].ff, val[kil.back().ss.ff].ff - 1)) <= val[i].ss){
			val[i].ss -= s;
			br = kil.back().ss.ff;
			val[i].ss += kil.back().ss.ss;
			kil.pop_back();
			if(kil.empty()){
				if(val[i].ss != 0)
					return 0;
				sp = 1;
				break;
			}
		}

		if(sp){
			kil.push_back({val[i].ff + 1, {M, 0}});
			continue;
		}

		for(int j = 20; j >= 0; --j){
			if(br + (1 << j) <= kil.back().ss.ff && (s = query(kil.back().ff, val[br].ff, val[i].ff, val[br + (1 << j)].ff - 1)) <= val[i].ss){
				val[i].ss -= s;
				br += 1 << j;
			}
		}
		kil.push_back({val[i].ff + 1, {br, val[i].ss}});
	}

	return 1;
}

Compilation message (stderr)

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

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