oj.uz

Submission #384907

# Submission time Handle Problem Language Result Execution time Memory
384907 2021-04-02T15:48:45 Z LucaDantas Teams (IOI15_teams) C++17
77 / 100
 3635 ms 269276 KB 
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;

#define all(a) (a).begin(), (a).end()

constexpr int maxn = 2e5+10;

int n, ind[maxn];

struct Node
{
	Node *l, *r;
	int v;
	Node() : l(this), r(this), v(0) {}
} *root[maxn];

struct PersistentSegmentTree
{
	Node* upd(Node* base, int i, int j, int pos, int v) {
		Node *node = new Node();
		*node = *base;
		node->v += v;
		if(i == j) return node;
		int m = (i+j) >> 1;
		if(pos <= m) node->l = upd(node->l, i, m, pos, v);
		else node->r = upd(node->r, m+1, j, pos, v);
		return node;
	}
	int query(Node* prev, Node* now, int i, int j, int l, int r) {
		if(i > r || j < l) return 0;
		if(i >= l && j <= r) return now->v - prev->v;
		int m = (i+j) >> 1;
		return query(prev->l, now->l, i, m, l, r) + query(prev->r, now->r, m+1, j, l, r);
	}
	int get(int l, int r, int k) {
		return query(root[ind[l]], root[ind[r]], 1, n, k, n);
	}
} seg;

pair<int,int> ranges[maxn];

void init(int N, int A[], int B[]) {
	n = N;
	for(int i = 0; i < N; i++)
		ranges[i] = {A[i], B[i]};
	sort(ranges, ranges+N);
	root[0] = new Node();
	for(int i = 1, ptr = 0; i <= N; i++) {
		for(; ptr < N && ranges[ptr].first == i; ptr++)
			root[ptr+1] = seg.upd(root[ptr], 1, n, ranges[ptr].second, 1);
		ind[i] = ptr;
	}
}

int fq[maxn];

long long dp[maxn]; // qual o menor valor de |v(S)| - |S| pra um subset até i

int can(int M, int K[]) {
	vector<int> V(M);
	for(int i = 0; i < M; i++)
		V[i] = K[i], ++fq[K[i]];
	sort(all(V));
	V.erase(unique(all(V)), V.end());
	M = (int)V.size();

	bool ok = 1;
	for(int i = 0; i < M; i++) {
		int k = V[i];
		dp[i] = seg.get(0, k, k) - 1ll * fq[k] * k;

		for(int j = 0; j < i; j++)
			dp[i] = min(dp[i], dp[j] + seg.get(V[j], k, k) - 1ll * fq[k] * k);

		ok &= dp[i] >= 0;
	}

	for(int i = 0; i < M; i++)
		dp[i] = fq[V[i]] = 0;

	return ok;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 58988 KB Output is correct
2 Correct 162 ms 59116 KB Output is correct
3 Correct 130 ms 58988 KB Output is correct
4 Correct 132 ms 59884 KB Output is correct
5 Correct 115 ms 58988 KB Output is correct
6 Correct 109 ms 59032 KB Output is correct
7 Correct 114 ms 58988 KB Output is correct
8 Correct 116 ms 58988 KB Output is correct
9 Correct 88 ms 57068 KB Output is correct
10 Correct 90 ms 56940 KB Output is correct
11 Correct 94 ms 60012 KB Output is correct
12 Correct 97 ms 56812 KB Output is correct
13 Correct 105 ms 59884 KB Output is correct
14 Correct 101 ms 57580 KB Output is correct
15 Correct 124 ms 59008 KB Output is correct
16 Correct 124 ms 59116 KB Output is correct
17 Correct 99 ms 59884 KB Output is correct
18 Correct 102 ms 59884 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3355 ms 59716 KB Output is correct
2 Correct 2953 ms 59584 KB Output is correct
3 Correct 240 ms 63084 KB Output is correct
4 Correct 131 ms 60524 KB Output is correct
5 Correct 3530 ms 60396 KB Output is correct
6 Correct 3050 ms 60312 KB Output is correct
7 Correct 3635 ms 60416 KB Output is correct
8 Correct 3097 ms 60140 KB Output is correct
9 Correct 89 ms 57360 KB Output is correct
10 Correct 93 ms 57452 KB Output is correct
11 Correct 148 ms 60780 KB Output is correct
12 Correct 1338 ms 58004 KB Output is correct
13 Correct 390 ms 61292 KB Output is correct
14 Correct 266 ms 62316 KB Output is correct
15 Correct 219 ms 60396 KB Output is correct
16 Correct 219 ms 60524 KB Output is correct
17 Correct 250 ms 61420 KB Output is correct
18 Correct 219 ms 61376 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 533 ms 269276 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -