#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
struct node {
int sum;
node* l;
node* r;
node() : sum(0), l(nullptr), r(nullptr) {}
};
const int kN = 5e5;
int n, ver[1 + kN], used[kN];
node *roots[1 + kN];
vector<int> rEnd[1 + kN];
vector<pair<int, int>> intervals;
void build(node *root, int lx, int rx) {
if (lx == rx) {
return;
}
int mid = (lx + rx) / 2;
root->l = new node;
build(root->l, lx, mid);
root->r = new node;
build(root->r, mid + 1, rx);
}
void update(node *prev, node *curr, int lx, int rx, int pos) {
if (lx == rx) {
curr->sum = prev->sum + 1;
return;
}
int mid = (lx + rx) / 2;
if (pos <= mid) {
curr->l = new node;
curr->r = prev->r;
update(prev->l, curr->l, lx, mid, pos);
} else {
curr->l = prev->l;
curr->r = new node;
update(prev->r, curr->r, mid + 1, rx, pos);
}
curr->sum = curr->l->sum + curr->r->sum;
}
int query(node *root, int lx, int rx, int st, int dr) {
if (st <= lx && rx <= dr) {
return root->sum;
}
int mid = (lx + rx) / 2;
int sum = 0;
if (st <= mid) {
sum += query(root->l, lx, mid, st, dr);
}
if (mid < dr) {
sum += query(root->r, mid + 1, rx, st, dr);
}
return sum;
}
void init(int N, int A[], int B[]) {
n = N;
for (int i = 0; i < N; ++i) {
rEnd[A[i]].emplace_back(B[i]);
}
roots[0] = new node;
build(roots[0], 1, n);
int version = 0;
for (int l = 1; l <= n; ++l) {
for (const int &r : rEnd[l]) {
version += 1;
roots[version] = new node;
update(roots[version - 1], roots[version], 1, n, r);
}
ver[l] = version;
}
}
int can(int m, int a[]) {
int sum = 0;
for (int i = 0; i < m; ++i) {
sum += a[i];
if (n < sum) {
return 0;
}
}
sort(a, a + m);
intervals.clear();
int last = a[0];
for (int i = 1; i < m; ++i) {
if (last != a[i]) {
intervals.emplace_back(last, a[i] - 1);
}
last = a[i];
}
intervals.emplace_back(last, n);
int R = intervals.size();
for (int i = 0; i < R; ++i) {
used[i] = 0;
}
int ptr = 0;
for (int i = 0; i < m; ++i) {
int j = i;
while (j < m && a[i] == a[j]) {
j += 1;
}
int req = a[i] * (j - i);
for (int k = ptr; k < R && req; ++k) {
int take = min(req, query(roots[ver[a[i]]], 1, n, intervals[k].first, intervals[k].second) - used[k]);
req -= take;
used[k] += take;
}
if (req) {
return 0;
}
i = j - 1;
ptr += 1;
}
return 1;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:123:25: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
123 | int R = intervals.size();
| ~~~~~~~~~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11996 KB |
Output is correct |
3 |
Correct |
7 ms |
12116 KB |
Output is correct |
4 |
Correct |
7 ms |
12008 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12116 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
9 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
12108 KB |
Output is correct |
10 |
Correct |
6 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
12116 KB |
Output is correct |
13 |
Correct |
7 ms |
11988 KB |
Output is correct |
14 |
Correct |
7 ms |
12064 KB |
Output is correct |
15 |
Correct |
7 ms |
11988 KB |
Output is correct |
16 |
Correct |
6 ms |
11988 KB |
Output is correct |
17 |
Correct |
7 ms |
11988 KB |
Output is correct |
18 |
Correct |
6 ms |
11988 KB |
Output is correct |
19 |
Correct |
7 ms |
12072 KB |
Output is correct |
20 |
Correct |
6 ms |
11988 KB |
Output is correct |
21 |
Correct |
7 ms |
11988 KB |
Output is correct |
22 |
Correct |
6 ms |
11960 KB |
Output is correct |
23 |
Correct |
7 ms |
11988 KB |
Output is correct |
24 |
Correct |
7 ms |
12040 KB |
Output is correct |
25 |
Correct |
7 ms |
11988 KB |
Output is correct |
26 |
Correct |
7 ms |
11988 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
134 ms |
77420 KB |
Output is correct |
2 |
Correct |
134 ms |
77464 KB |
Output is correct |
3 |
Correct |
150 ms |
77432 KB |
Output is correct |
4 |
Correct |
133 ms |
77828 KB |
Output is correct |
5 |
Correct |
81 ms |
76208 KB |
Output is correct |
6 |
Correct |
84 ms |
76260 KB |
Output is correct |
7 |
Correct |
83 ms |
76216 KB |
Output is correct |
8 |
Correct |
88 ms |
76236 KB |
Output is correct |
9 |
Correct |
76 ms |
73948 KB |
Output is correct |
10 |
Correct |
79 ms |
73944 KB |
Output is correct |
11 |
Correct |
99 ms |
76996 KB |
Output is correct |
12 |
Correct |
86 ms |
73904 KB |
Output is correct |
13 |
Correct |
89 ms |
77076 KB |
Output is correct |
14 |
Correct |
94 ms |
75332 KB |
Output is correct |
15 |
Correct |
119 ms |
77228 KB |
Output is correct |
16 |
Correct |
127 ms |
77260 KB |
Output is correct |
17 |
Correct |
84 ms |
77084 KB |
Output is correct |
18 |
Correct |
95 ms |
77040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
154 ms |
77804 KB |
Output is correct |
2 |
Correct |
160 ms |
77836 KB |
Output is correct |
3 |
Correct |
207 ms |
80784 KB |
Output is correct |
4 |
Correct |
124 ms |
77852 KB |
Output is correct |
5 |
Correct |
107 ms |
76620 KB |
Output is correct |
6 |
Correct |
103 ms |
76644 KB |
Output is correct |
7 |
Correct |
97 ms |
76596 KB |
Output is correct |
8 |
Correct |
99 ms |
76560 KB |
Output is correct |
9 |
Correct |
76 ms |
73948 KB |
Output is correct |
10 |
Correct |
90 ms |
74228 KB |
Output is correct |
11 |
Correct |
106 ms |
77316 KB |
Output is correct |
12 |
Correct |
828 ms |
74328 KB |
Output is correct |
13 |
Correct |
264 ms |
77612 KB |
Output is correct |
14 |
Correct |
241 ms |
78928 KB |
Output is correct |
15 |
Correct |
147 ms |
77772 KB |
Output is correct |
16 |
Correct |
145 ms |
77724 KB |
Output is correct |
17 |
Correct |
106 ms |
77492 KB |
Output is correct |
18 |
Correct |
100 ms |
77384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
914 ms |
375236 KB |
Output is correct |
2 |
Correct |
883 ms |
375256 KB |
Output is correct |
3 |
Correct |
1240 ms |
381132 KB |
Output is correct |
4 |
Correct |
838 ms |
375364 KB |
Output is correct |
5 |
Correct |
472 ms |
368928 KB |
Output is correct |
6 |
Correct |
450 ms |
368908 KB |
Output is correct |
7 |
Correct |
439 ms |
368888 KB |
Output is correct |
8 |
Correct |
452 ms |
368896 KB |
Output is correct |
9 |
Correct |
371 ms |
353212 KB |
Output is correct |
10 |
Correct |
406 ms |
368964 KB |
Output is correct |
11 |
Correct |
1426 ms |
369080 KB |
Output is correct |
12 |
Correct |
2614 ms |
369124 KB |
Output is correct |
13 |
Correct |
1045 ms |
370324 KB |
Output is correct |
14 |
Correct |
1115 ms |
375208 KB |
Output is correct |
15 |
Correct |
720 ms |
374148 KB |
Output is correct |
16 |
Correct |
719 ms |
374032 KB |
Output is correct |
17 |
Correct |
467 ms |
369412 KB |
Output is correct |
18 |
Correct |
465 ms |
369320 KB |
Output is correct |