QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#605599 | #9221. Missing Boundaries | ucup-team3215# | WA | 73ms | 10456kb | C++23 | 3.1kb | 2024-10-02 18:08:27 | 2024-10-02 18:08:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string yes = "TAK", no = "NIE";
void solve() {
int n, k;
cin >> n >> k;
int fr = 0;
vector<array<int, 2>> all;
vector<int> L, R, A;
for (int i = 0; i < n; ++i) {
int l, r;
cin >> l >> r;
if (!~l && !~r) {
++fr;
continue;
}
if (~l && ~r) {
all.push_back({l, r});
continue;
}
if (~l) {
L.push_back(l);
A.push_back(l);
} else {
R.push_back(r);
A.push_back(r);
}
}
vector<array<int, 2>> delta;
for (auto [l, r]: all) {
delta.push_back({l, 1});
delta.push_back({r + 1, -1});
}
sort(delta.begin(), delta.end());
int cur = 0;
for (auto [_, x]: delta) {
cur += x;
if (cur > 1) {
cout << no << "\n";
return;
}
}
sort(A.begin(), A.end());
A.resize(unique(A.begin(), A.end()) - A.begin());
if (A.size() != L.size() + R.size()) {
cout << no << "\n";
return;
}
int len = A.size();
for (auto [l, r]: all) {
len += r - l + 1;
auto it = lower_bound(A.begin(), A.end(), l);
if (it != A.end() && *it <= r) {
cout << no << "\n";
return;
}
}
vector<int> z;
sort(all.begin(), all.end());
if (all.size() && all[0][0] > 1)z.push_back(1);
bool en = true;
for (int i = 0; i < all.size(); ++i) {
en = false;
if (z.back() != all[i][0])z.push_back(all[i][0]);
if (all[i][1] + 1 <= k) {
z.push_back(all[i][1] + 1);
en = true;
}
}
if (en)z.push_back(k + 1);
int q = z.size();
vector<vector<pair<int, char>>> val(q);
for (auto x: L) {
auto it = upper_bound(z.begin(), z.end(), x);
assert(it != z.begin());
--it;
val[it - z.begin()].push_back({x, 'L'});
}
for (auto x: R) {
auto it = upper_bound(z.begin(), z.end(), x);
assert(it != z.begin());
--it;
val[it - z.begin()].push_back({x, 'R'});
}
int mx = k - len;
int mn = 0;
for (int i = 0; i < q; i += 2) {
pair<int, char> last = {z[i], 'R'};
sort(val[i].begin(), val[i].end());
for (auto [x, c]: val[i]) {
if (c == 'R') {
if (last.second == 'L') {
last = {x + 1, 'R'};
} else {
last = {x + 1, 'R'};
}
} else {
if (last.second == 'L') {
last = {x + 1, 'L'};
} else {
mn += x != last.first;
last = {x + 1, 'L'};
}
}
}
if (last.second == 'R' && last.first != z[i + 1])++mn;
}
cout << (fr >= mn && fr <= mx? yes : no) << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(false);
ll t;
cin >> t;
while (t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
3 4 51 1 -1 11 50 -1 -1 -1 10 3 2 -1 -1 -1 -1 -1 -1 2 3 1 2 2 3
output:
TAK NIE NIE
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 73ms
memory: 10456kb
input:
1 200000 1000000000 490669427 -1 224278942 224287156 821104480 -1 861696576 861702036 807438935 807440055 574078002 574083717 465630141 -1 195378188 -1 -1 13500961 -1 977536179 92893115 -1 -1 661145418 -1 215804863 -1 685338515 544348999 -1 465532902 -1 130346949 -1 -1 526666304 635604584 635605404 ...
output:
NIE
result:
wrong answer 1st lines differ - expected: 'TAK', found: 'NIE'