oj.uz

답안 #765336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765336 2023-06-24T11:01:07 Z loctildore 팀들 (IOI15_teams) C++14
100 / 100
 1773 ms 133140 KB 
#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;
}

Compilation message

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.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 308 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 1 ms 308 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 27144 KB Output is correct
2 Correct 172 ms 26740 KB Output is correct
3 Correct 158 ms 25340 KB Output is correct
4 Correct 153 ms 25920 KB Output is correct
5 Correct 23 ms 16844 KB Output is correct
6 Correct 28 ms 16308 KB Output is correct
7 Correct 23 ms 16920 KB Output is correct
8 Correct 28 ms 16852 KB Output is correct
9 Correct 53 ms 25456 KB Output is correct
10 Correct 25 ms 16160 KB Output is correct
11 Correct 26 ms 18424 KB Output is correct
12 Correct 34 ms 20192 KB Output is correct
13 Correct 57 ms 22388 KB Output is correct
14 Correct 111 ms 26276 KB Output is correct
15 Correct 122 ms 24676 KB Output is correct
16 Correct 118 ms 24648 KB Output is correct
17 Correct 26 ms 16776 KB Output is correct
18 Correct 32 ms 19108 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 272 ms 28052 KB Output is correct
2 Correct 238 ms 27956 KB Output is correct
3 Correct 200 ms 29476 KB Output is correct
4 Correct 137 ms 25868 KB Output is correct
5 Correct 76 ms 17632 KB Output is correct
6 Correct 72 ms 17612 KB Output is correct
7 Correct 52 ms 17636 KB Output is correct
8 Correct 67 ms 17664 KB Output is correct
9 Correct 54 ms 25408 KB Output is correct
10 Correct 24 ms 16620 KB Output is correct
11 Correct 33 ms 18680 KB Output is correct
12 Correct 203 ms 20576 KB Output is correct
13 Correct 291 ms 23104 KB Output is correct
14 Correct 263 ms 27784 KB Output is correct
15 Correct 157 ms 25632 KB Output is correct
16 Correct 144 ms 25524 KB Output is correct
17 Correct 51 ms 18428 KB Output is correct
18 Correct 60 ms 21084 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1773 ms 129708 KB Output is correct
2 Correct 1622 ms 129816 KB Output is correct
3 Correct 1382 ms 133136 KB Output is correct
4 Correct 1208 ms 125584 KB Output is correct
5 Correct 289 ms 76920 KB Output is correct
6 Correct 263 ms 77448 KB Output is correct
7 Correct 192 ms 77504 KB Output is correct
8 Correct 253 ms 76592 KB Output is correct
9 Correct 338 ms 131936 KB Output is correct
10 Correct 142 ms 83428 KB Output is correct
11 Correct 284 ms 93024 KB Output is correct
12 Correct 807 ms 105112 KB Output is correct
13 Correct 1134 ms 107648 KB Output is correct
14 Correct 1562 ms 133140 KB Output is correct
15 Correct 941 ms 119448 KB Output is correct
16 Correct 911 ms 118460 KB Output is correct
17 Correct 248 ms 90800 KB Output is correct
18 Correct 256 ms 91324 KB Output is correct