oj.uz

답안 #541100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541100 2022-03-22T08:25:33 Z GioChkhaidze 팀들 (IOI15_teams) C++14
100 / 100
 1402 ms 146072 KB 
#include <bits/stdc++.h>
#include "teams.h"

#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define pb push_back
#define f first
#define s second

using namespace std;

const int Nn = 5e5 + 5;

bool used[Nn];
int n, m, cost, a[Nn], b[Nn], k[Nn], dp[Nn], pr[Nn], nx[Nn], mpr[Nn];
vector < int > v[4* Nn], O[Nn];

void build(tree) {
	if (l == r) {
		v[h] = O[l];
		return;
	}
	build(left), build(right);
	int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
	while (li < ls || ri < rs) {
		if (li < ls && (ri == rs || v[lf][li] <= v[rf][ri])) {
			v[h].pb(v[lf][li++]);
		}
			else
		if (ri < rs && (li == ls || v[rf][ri] <= v[lf][li])) {
			v[h].pb(v[rf][ri++]);
		}
	} 
}

int Mn, Mx, id;
int g(int h) {
	int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
	int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
	return max(0, r - l);
} 

int get(tree) {
	if (l == r) return g(h);
	if (Mx <= mf) return get(left) + g(rf);
	return get(right);
}

int Get(tree, int vl) {
	if (l == r) {
		if (g(h) <= vl) return l;
		return n + 1;
	}
	int rc = g(rf);
	if (rc <= vl) 
		return min(mf + 1, Get(left, vl - rc));
	return Get(right, vl); 
}

int Mm(int tl, int tr) {
	/*int l = k[tr] + 1, r = n, res = n + 1, mid;
	while (l <= r) {
		mid = ((l + r) >> 1), Mx = mid;
		Mn = k[tl] + 1;
		int I = dp[tl] + get(1, 1, n);
		Mn = k[tr] + 1;
		int J = dp[tr] + get(1, 1, n);
		if (I <= J) 
			res = mid, r = mid - 1;
				else 
			l = mid + 1;
	}
	return res;*/
	Mn = k[tl] + 1, Mx = k[tr];
	return Get(1, 1, n, dp[tr] - dp[tl]);
}

/*
i < j
dp[i] + solve(i, k) <= dp[j] + solve(j, k);

dp[j] - dp[i] >= solve(i, k) - solve(j, k)

mid = {k[j] + 1, n}

dp[j] - dp[i] >= solve(i, mid) - solve(j, mid)

max number of a,b such that a in (k[i] + 1, k[j])  b in (k[mid], n)

how many a,b   a in (k[i] + 1, k[k])  b in (k[k], n)
how many a,b   a in (k[j] + 1, k[k])  b in (k[k], n)
*/

void init(int N, int A[], int B[]) {
	n = N;
	for (int i = 1; i <= n; ++i) {
		a[i] = A[i - 1];
		b[i] = B[i - 1];
		O[b[i]].pb(a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		sort(O[i].begin(), O[i].end());
	}
	build(1, 1, n);
}

int can(int M, int K[]) {
	m = M;
	ll sum = 0;
	for (int i = 1; i <= m; ++i) {
		pr[i] = nx[i] = used[i] = 0;
		k[i] = K[i - 1];
		sum += k[i];
	}
	sort(k + 1, k + m + 1);
	if (sum > n) return 0;
	set < pair < int , int > > st;
	vector < int > dq;
	dq.push_back(0);
	// get(1, 1, n);
	// how many a,b   a in (k[l] + 1, k[i])  b in (k[i], n)
	for (int i = 1; i <= m; ++i) {
		while (st.size() && (*st.begin()).f <= k[i]) {
			int mo = (*st.begin()).f;
			int id = (*st.begin()).s;
			st.erase(st.find({mo, id}));
			used[id] = true;
			// was erased pr[id] -> id
			int tl = pr[id], tr = nx[id];
			if (tr) {
				// erase id -> nx[id]
				st.erase({mpr[tr], tr});
				mpr[tr] = Mm(tl, tr);
				// insert pr[id] -> nx[id]
				st.insert({mpr[tr], tr});
				nx[tl] = tr, pr[tr] = tl;
			}
		}
		// find dp[i];
		while (used[dq.back()]) {
			dq.pop_back();
		}
		int l = dq.back();
		Mn = k[l] + 1, Mx = k[i];
		//if (Mn <= Mx) 
		cost = get(1, 1, n);
		//		else 
		//	cost = 0;
		dp[i] = dp[l] - k[i] + cost;
		if (dp[i] < 0) return false;
		dq.push_back(i);
		mpr[i] = Mm(l, i);
		pr[i] = l, nx[l] = i;
		st.insert({mpr[i], i});
	}
	return true;
}

Compilation message

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:29:38: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |  int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
      |                            ~~~~~~~~~~^~
teams.cpp:29:57: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |  int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
      |                                               ~~~~~~~~~~^~
teams.cpp: In function 'int g(int)':
teams.cpp:43:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   43 |  int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:44:57: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   44 |  int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:130:8: warning: declaration of 'id' shadows a global declaration [-Wshadow]
  130 |    int id = (*st.begin()).s;
      |        ^~
teams.cpp:41:13: note: shadowed declaration is here
   41 | int Mn, Mx, id;
      |             ^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 58956 KB Output is correct
2 Correct 27 ms 58956 KB Output is correct
3 Correct 28 ms 59068 KB Output is correct
4 Correct 27 ms 59012 KB Output is correct
5 Correct 30 ms 58952 KB Output is correct
6 Correct 30 ms 59152 KB Output is correct
7 Correct 27 ms 58992 KB Output is correct
8 Correct 28 ms 58964 KB Output is correct
9 Correct 28 ms 58964 KB Output is correct
10 Correct 30 ms 58996 KB Output is correct
11 Correct 28 ms 58964 KB Output is correct
12 Correct 29 ms 58992 KB Output is correct
13 Correct 29 ms 59040 KB Output is correct
14 Correct 28 ms 58964 KB Output is correct
15 Correct 27 ms 58972 KB Output is correct
16 Correct 28 ms 59068 KB Output is correct
17 Correct 28 ms 59060 KB Output is correct
18 Correct 28 ms 58964 KB Output is correct
19 Correct 28 ms 59040 KB Output is correct
20 Correct 27 ms 58964 KB Output is correct
21 Correct 29 ms 59052 KB Output is correct
22 Correct 29 ms 59016 KB Output is correct
23 Correct 33 ms 59092 KB Output is correct
24 Correct 29 ms 58964 KB Output is correct
25 Correct 30 ms 59000 KB Output is correct
26 Correct 28 ms 58964 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 74612 KB Output is correct
2 Correct 85 ms 74724 KB Output is correct
3 Correct 93 ms 74820 KB Output is correct
4 Correct 89 ms 76312 KB Output is correct
5 Correct 46 ms 69776 KB Output is correct
6 Correct 46 ms 69632 KB Output is correct
7 Correct 44 ms 69628 KB Output is correct
8 Correct 43 ms 69660 KB Output is correct
9 Correct 81 ms 70492 KB Output is correct
10 Correct 51 ms 69208 KB Output is correct
11 Correct 49 ms 68664 KB Output is correct
12 Correct 44 ms 68224 KB Output is correct
13 Correct 53 ms 69256 KB Output is correct
14 Correct 62 ms 71308 KB Output is correct
15 Correct 79 ms 74184 KB Output is correct
16 Correct 80 ms 74252 KB Output is correct
17 Correct 49 ms 69416 KB Output is correct
18 Correct 49 ms 69600 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 74792 KB Output is correct
2 Correct 92 ms 74736 KB Output is correct
3 Correct 305 ms 77712 KB Output is correct
4 Correct 86 ms 76232 KB Output is correct
5 Correct 142 ms 69748 KB Output is correct
6 Correct 129 ms 69700 KB Output is correct
7 Correct 53 ms 69700 KB Output is correct
8 Correct 107 ms 69772 KB Output is correct
9 Correct 83 ms 70532 KB Output is correct
10 Correct 85 ms 69672 KB Output is correct
11 Correct 85 ms 68872 KB Output is correct
12 Correct 106 ms 68380 KB Output is correct
13 Correct 236 ms 69512 KB Output is correct
14 Correct 376 ms 75184 KB Output is correct
15 Correct 177 ms 74436 KB Output is correct
16 Correct 181 ms 74308 KB Output is correct
17 Correct 165 ms 69644 KB Output is correct
18 Correct 158 ms 69568 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 441 ms 140076 KB Output is correct
2 Correct 420 ms 140020 KB Output is correct
3 Correct 1096 ms 144636 KB Output is correct
4 Correct 414 ms 142908 KB Output is correct
5 Correct 435 ms 113920 KB Output is correct
6 Correct 389 ms 113996 KB Output is correct
7 Correct 119 ms 113964 KB Output is correct
8 Correct 326 ms 114044 KB Output is correct
9 Correct 336 ms 118992 KB Output is correct
10 Correct 199 ms 110520 KB Output is correct
11 Correct 205 ms 109400 KB Output is correct
12 Correct 267 ms 109516 KB Output is correct
13 Correct 815 ms 113172 KB Output is correct
14 Correct 1402 ms 146072 KB Output is correct
15 Correct 579 ms 141628 KB Output is correct
16 Correct 576 ms 141496 KB Output is correct
17 Correct 440 ms 118400 KB Output is correct
18 Correct 420 ms 118324 KB Output is correct