Submission #765245

#	Time	Username	Problem	Language	Result	Execution time	Memory
765245		loctildore	Teams (IOI15_teams)	C++14	77 / 100	4062 ms	127968 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)

struct node {
	int l, r;
	node *lft, *rht;
	vector<int> endp;
	node(int tl, int tr): l(tl), r(tr) {
		if (l + 1 == r) {
			lft = rht = NULL;
			return;
		}
		lft = new node(l, (l + r) / 2);
		rht = new node((l + r) / 2, r);
	}

	void upd(int tl, int tr) {
		if (tr <= l || r <= tl) {
			return;
		}
		if (tl <= l && r <= tr) {
			endp.push_back(tr - 1);
			return;
		}
		lft->upd(tl, tr);
		rht->upd(tl, tr);
	}

	void srt() {
		sort(all(endp));
		if (l + 1 != r) {
			lft->srt();
			rht->srt();
		}
	}

	int has(int x, int y) {
		if (x < l || r <= x) {
			return 0;
		}
		int rtn = end(endp) - lower_bound(all(endp), y);
		if (l + 1 != r) {
			rtn += lft->has(x, y);
			rtn += rht->has(x, y);
		}
		return rtn;
	}
} *root;

int n;

void init(int N, int A[], int B[]) {
	n = N;
	root = new node(0, n + 69);
	for (int i = 0; i < n; i++) {
		root->upd(A[i], B[i] + 1);
	}
	root->srt();
}

vector<pair<int,int>> vctr;
int m;
int carr[1069][1069];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
int can(int M, int K[]) {
	int tot = 0;
	vctr.clear();
	while (pq.size()) pq.pop();
	map<int, int> mp;
	for (int i = 0; i < M; i++) {
		tot += K[i];
		mp[K[i]] += K[i];
	}
	for (auto t : mp) {
		vctr.push_back(t);
	}
	m = vctr.size();
	if (tot > n) return 0;
	sort(all(vctr));
	for (int i = 0; i < m; i++) {
		for (int j = i; j < m; j++) {
			carr[i][j] = root->has(vctr[i].f, vctr[j].f);
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = i; j < m; j++) {
			int tmp = carr[i][j];
			if (i > 0) tmp -= carr[i - 1][j];
			if (j + 1 < m) tmp -= carr[i][j + 1];
			if (i > 0 && j + 1 < m) tmp += carr[i - 1][j + 1];
			if (tmp) {
				pq.push({j, tmp});
			}
			//cout<<i<<j<<':'<<carr[i][j]<<' '<<endl;
		}
		//cout<<endl;
		while (pq.size() && pq.top().f < i) pq.pop();
		int tmp = vctr[i].s;
		while (tmp && pq.size()) {
			auto t = pq.top(); pq.pop();
			int sub = min(tmp, t.s);
			tmp -= sub;
			t.s -= sub;
			if (t.s) pq.push(t);
		}
		if (tmp) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int node::has(int, int)':
teams.cpp:47:23: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   47 |   int rtn = end(endp) - lower_bound(all(endp), y);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:83:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   83 |  m = vctr.size();
      |      ~~~~~~~~~^~

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