/*
* author: ADMathNoob
* created: 04/22/21 14:39:48
* problem: https://www.acmicpc.net/problem/8242
*/
/*
g++ boj_8242.cpp -D_DEBUG -std=c++11 -Wl,--stack=268435456 -Wall -Wfatal-errors -ggdb && gdb a
g++ boj_8242.cpp -D_DEBUG -std=c++11 -Wl,--stack=268435456 -O3 -Wall -Wfatal-errors
Try to avoid O(n log^2(n)) per case?
pessimistic
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
vector<int> when(m);
vector<int> who(m);
vector<int> others(m);
for (int j = 0; j < m; j++) {
cin >> when[j] >> who[j] >> others[j];
--when[j];
--who[j];
}
int low = 0, high = m;
while (low < high) {
int mid = (low + high + 1) >> 1;
vector<int> cnt(m, -1);
bool ok = true;
vector<int> first(n, m);
vector<int> last(n, -1);
// check that the claims are consistent for each point in time
for (int j = 0; j < mid; j++) {
int t = when[j];
if (cnt[t] != -1 && cnt[t] != others[j] + 1) {
ok = false;
}
cnt[t] = others[j] + 1;
first[who[j]] = min(first[who[j]], t);
last[who[j]] = max(last[who[j]], t);
// assert(0 <= first[who[j]] && first[who[j]] <= last[who[j]] && last[who[j]] < m);
} // OK
if (!ok) {
high = mid - 1;
continue;
}
// cerr << "first " << mid << ": at first glance, consistent\n";
{
// check that there aren't times with too many people already
vector<int> a(m + 1, 0);
for (int i = 0; i < n; i++) {
if (first[i] != m) {
a[first[i]] += 1;
a[last[i] + 1] -= 1;
}
}
for (int t = 0; t < m; t++) {
if (cnt[t] != -1 && a[t] > cnt[t]) {
// cerr << "too many people at time " << t << '\n';
ok = false;
}
a[t + 1] += a[t];
}
assert(a[m] == 0);
if (!ok) {
high = mid - 1;
continue;
}
} // OK
vector<int> add(m, 0);
vector<int> remove(m, 0);
for (int i = 0; i < n; i++) {
if (first[i] != m) {
add[first[i]] += 1;
remove[last[i]] += 1;
}
}
{
// extend intervals right
vector<int> new_remove(m, 0);
int in = 0; // in the office
for (int t = 0; t < m; t++) {
in += add[t];
if (cnt[t] != -1) {
if (in > cnt[t]) {
int drop = in - cnt[t];
// cerr << "too many at time " << t << "; removing " << drop << "\n";
assert(t > 0);
new_remove[t - 1] = drop;
in -= drop;
}
}
}
new_remove[m - 1] = in;
remove = new_remove;
assert(accumulate(add.begin(), add.end(), 0) == accumulate(remove.begin(), remove.end(), 0));
} // OK
{
// extend intervals left
vector<int> new_add(m, 0);
int in = 0;
for (int t = m - 1; t >= 0; t--) {
in += remove[t];
if (cnt[t] != -1) {
if (in > cnt[t]) {
int drop = in - cnt[t];
assert(t < m - 1);
new_add[t + 1] = drop;
in -= drop;
}
}
}
new_add[0] = in;
add = new_add;
assert(accumulate(add.begin(), add.end(), 0) == accumulate(remove.begin(), remove.end(), 0));
} // OK
{
// check that there aren't times with too many people again
vector<int> a(m + 1, 0);
for (int i = 0; i < n; i++) {
if (first[i] != m) {
a[first[i]] += 1;
a[last[i] + 1] -= 1;
}
}
for (int t = 0; t < m; t++) {
assert(cnt[t] == -1 || a[t] <= cnt[t]);
a[t + 1] += a[t];
}
}
// cerr << "add remove\n";
// for (int i = 0; i < m; i++) {
// cerr << add[i] << ' ' << remove[i] << '\n';
// }
// cerr << '\n';
int in = 0;
// cerr << unused << " people unaccounted for\n";
int needed = 0;
for (int t = 0; t < m; t++) {
in += add[t];
if (cnt[t] != -1) {
if (in < cnt[t]) {
needed += cnt[t] - in;
}
in = cnt[t];
}
in -= remove[t];
// assert(in >= 0);
}
int extras = count(first.begin(), first.end(), m);
if (needed > extras) {
ok = false;
}
if (ok) {
low = mid;
} else {
high = mid - 1;
}
}
cout << low << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
332 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
328 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
564 KB |
Output isn't correct |
| 7 |
Incorrect |
22 ms |
748 KB |
Output isn't correct |
| 8 |
Incorrect |
124 ms |
3312 KB |
Output isn't correct |
| 9 |
Incorrect |
285 ms |
6544 KB |
Output isn't correct |
| 10 |
Incorrect |
589 ms |
13156 KB |
Output isn't correct |
| 11 |
Incorrect |
827 ms |
17512 KB |
Output isn't correct |
| 12 |
Incorrect |
1753 ms |
36060 KB |
Output isn't correct |
| 13 |
Incorrect |
1518 ms |
34700 KB |
Output isn't correct |
