제출 #765336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765336		loctildore	Teams (IOI15_teams)	C++14	100 / 100	1773 ms	133140 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)

int m;
vector<pair<int,int>> vctr;
int carr[1069][1069];

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;
	}

	void chckhas(int x) {
		if (vctr[x].f < l || r <= vctr[x].f) return;
		int tmp = 0;
		if (endp.size()) for (int j = x; j < m; j++) {
			if (endp[tmp] < vctr[j].f) {
				tmp = lower_bound(begin(endp) + tmp, end(endp), vctr[j].f) - begin(endp);
			}
			carr[x][j] += endp.size() - tmp;
			if (!carr[x][j]) break;
		}
		if (l + 1 != r) {
			lft->chckhas(x);
			rht->chckhas(x);
			/*if (vctr[x].f < (l + r) / 2) {
				lft->chckhas(x);
			}
			else rht->chckhas(x);*/
		}
	}
} *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();
}

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] = 0;
			//carr[i][j] = root->has(vctr[i].f, vctr[j].f);
			//if (!carr[i][j]) break;
		}
		root->chckhas(i);
	}
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In member function 'int node::has(int, int)':
teams.cpp:51:23: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   51 |   int rtn = end(endp) - lower_bound(all(endp), y);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'void node::chckhas(int)':
teams.cpp:64:64: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   64 |     tmp = lower_bound(begin(endp) + tmp, end(endp), vctr[j].f) - begin(endp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp:66:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   66 |    carr[x][j] += endp.size() - tmp;
      |                                ^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:104:15: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  104 |  m = vctr.size();
      |      ~~~~~~~~~^~

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