oj.uz

답안 #1049516

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1049516 2024-08-08T20:22:15 Z TAhmed33 팀들 (IOI15_teams) C++
77 / 100
 1958 ms 47164 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
const int MAXN = 1e5 + 25;
const int SZE = 400;
int n;
array <int, 2> a[MAXN];
struct SegmentTree {
	int tree[MAXN << 5], tl[MAXN << 5], tr[MAXN << 5];
	int cnt;
	int new_node (int x, int y) {
		++cnt; tl[cnt] = x; tr[cnt] = y;
		tree[cnt] = tree[x] + tree[y];
		return cnt;
	}
	int build (int l, int r) {
		if (l == r) {
			return ++cnt;
		}
		return new_node(build(l, mid), build(mid + 1, r));
	}
	int update (int l, int r, int a, int b, int node) {
		if (l == r) {
			cnt++; tree[cnt] = tree[node] + b;
			return cnt;
		}
		if (a <= mid) {
			return new_node(update(l, mid, a, b, tl[node]), tr[node]);
		} else {
			return new_node(tl[node], update(mid + 1, r, a, b, tr[node]));
		}
	}
	int get (int l, int r, int a, int b, int node) {
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) return tree[node];
		return get(l, mid, a, b, tl[node]) + get(mid + 1, r, a, b, tr[node]);
	}
} cur;
vector <int> upd[MAXN];
int roots[MAXN];
void init(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		a[i][0] = A[i];
	}
	for (int i = 0; i < n; i++) {
		a[i][1] = B[i];
	}
	sort(a, a + n);
	roots[0] = cur.build(1, n);
	for (int i = 0; i < n; i++) {
		upd[a[i][0]].push_back(a[i][1]);
	}
	for (int i = 1; i <= n; i++) {
		roots[i] = roots[i - 1];
		for (auto j : upd[i]) {
			roots[i] = cur.update(1, n, j, 1, roots[i]);
		}
	}
}
vector <array <int, 3>> ee[MAXN];
int query (int x1, int y1, int x2, int y2) {
	if (x1 > x2 || y1 > y2) return 0;
	return cur.get(1, n, y1, y2, roots[x2]) - cur.get(1, n, y1, y2, roots[x1 - 1]);
}
int can (int m, int k[]) {
	int sum = 0;
	for (int i = 0; i < m; i++) {
		sum += k[i];
		if (sum > n) {
			return 0;
		}
	}
	sort(k, k + m);
	if (m >= SZE) {
		for (int i = 1; i <= n; i++) {
			ee[i].clear();
		}
		for (int i = 0; i < n; i++) {
			ee[a[i][0]].push_back({a[i][1], i, 1});
			ee[a[i][1] + 1].push_back({a[i][1], i, -1});
		}
		int ptr = 1;
		set <array <int, 2>> cur;
		for (int i = 0; i < m; i++) {
			while (ptr <= k[i]) {
				for (auto j : ee[ptr]) {
					if (j[2] == 1) {
						cur.insert({j[0], j[1]});
					} else {
						cur.erase({j[0], j[1]});
					}
				}
				ptr++;
			}
			if (cur.size() < k[i]) {
				return 0;
			}
			for (int j = 0; j < k[i]; j++) {
				cur.erase(cur.begin());
			}
		}
		return 1;
	}
	long long dp[m] = {};
	for (int i = 0; i < m; i++) {
		dp[i] = query(1, k[i], k[i], n);
		for (int j = 0; j < i; j++) {
			dp[i] = min(dp[i], dp[j] + query(k[j] + 1, k[i], k[i], n));
		}
		dp[i] -= k[i];
	}
	return *min_element(dp, dp + m) >= 0;
}

Compilation message

teams.cpp: In member function 'int SegmentTree::update(int, int, int, int, int)':
teams.cpp:23:32: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   23 |  int update (int l, int r, int a, int b, int node) {
      |                            ~~~~^
teams.cpp:8:16: note: shadowed declaration is here
    8 | array <int, 2> a[MAXN];
      |                ^
teams.cpp: In member function 'int SegmentTree::get(int, int, int, int, int)':
teams.cpp:34:29: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   34 |  int get (int l, int r, int a, int b, int node) {
      |                         ~~~~^
teams.cpp:8:16: note: shadowed declaration is here
    8 | array <int, 2> a[MAXN];
      |                ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:85:24: warning: declaration of 'cur' shadows a global declaration [-Wshadow]
   85 |   set <array <int, 2>> cur;
      |                        ^~~
teams.cpp:39:3: note: shadowed declaration is here
   39 | } cur;
      |   ^~~
teams.cpp:97:19: warning: comparison of integer expressions of different signedness: 'std::set<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |    if (cur.size() < k[i]) {
      |        ~~~~~~~~~~~^~~~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 44112 KB Output is correct
2 Correct 38 ms 40268 KB Output is correct
3 Correct 31 ms 40280 KB Output is correct
4 Correct 40 ms 44624 KB Output is correct
5 Correct 27 ms 42320 KB Output is correct
6 Correct 22 ms 38944 KB Output is correct
7 Correct 19 ms 42164 KB Output is correct
8 Correct 21 ms 42332 KB Output is correct
9 Correct 30 ms 46052 KB Output is correct
10 Correct 32 ms 45908 KB Output is correct
11 Correct 36 ms 45884 KB Output is correct
12 Correct 19 ms 38864 KB Output is correct
13 Correct 21 ms 39108 KB Output is correct
14 Correct 20 ms 39368 KB Output is correct
15 Correct 33 ms 40140 KB Output is correct
16 Correct 29 ms 40020 KB Output is correct
17 Correct 18 ms 39004 KB Output is correct
18 Correct 19 ms 39000 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 341 ms 44660 KB Output is correct
2 Correct 881 ms 44840 KB Output is correct
3 Correct 79 ms 44112 KB Output is correct
4 Correct 39 ms 45904 KB Output is correct
5 Correct 1958 ms 43716 KB Output is correct
6 Correct 1797 ms 43904 KB Output is correct
7 Correct 302 ms 43860 KB Output is correct
8 Correct 1504 ms 43604 KB Output is correct
9 Correct 31 ms 46912 KB Output is correct
10 Correct 119 ms 47040 KB Output is correct
11 Correct 841 ms 47164 KB Output is correct
12 Correct 988 ms 40316 KB Output is correct
13 Correct 152 ms 40856 KB Output is correct
14 Correct 81 ms 43660 KB Output is correct
15 Correct 105 ms 42108 KB Output is correct
16 Correct 108 ms 41912 KB Output is correct
17 Correct 185 ms 40784 KB Output is correct
18 Correct 187 ms 40844 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 25680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -