QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #723021 | #9221. Missing Boundaries | lvliang | WA | 109ms | 14604kb | C++14 | 1.9kb | 2024-11-07 20:57:23 | 2024-11-07 20:57:23 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
PII pa[N];
void solve() {
int n, L;
scanf("%d%d", &n, &L);
int un_def = 0;
int idx = 0;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
if (y == -1 && x == -1) un_def++;
else {
if (x == -1) x = y, mp[x] = 1;
if (y == -1) y = x, mp[x] = 2;
pa[idx++] = { x, y };
}
}
sort(pa, pa + idx);
for (int i = 1; i < idx; i++) {
if (pa[i].fi <= pa[i - 1].se) {
puts("NIE");
return;
}
}
int r = 0;
// int st = L;
// for (int i = 0; i < idx; i++) {
// if (i && pa[i - 1].se == -1) {
// //r += pa[i].fi - pa[i - 1].se - 1;
// r += pa[i - 1].fi - pa[i].fi - 1;
// } else if (pa[i].fi < st) {
// l += st - pa[i].fi;
// }
// if (pa[i].se != -1) {
// st = pa[i].se - 1;
// }
// }
// if (pa[idx - 1].se == -1) {
// r += pa[idx - 1].fi - 1;
// } else l += pa[idx - 1].se - 1;
int st = 1;
for (int i = 0; i < idx; i++) {
if (pa[i].fi > st) {
if (mp[pa[i].fi] == 1) {
r += pa[i].fi - st;
st = pa[i].fi + 1;
} else if (--un_def == 0) {
puts("NIE");
return;
}
}
if (i + 1 == idx) break;
if (mp[pa[i].fi] == 2) {
st = pa[i + 1].fi;
r += st - pa[i].fi - 1;
} else {
st = pa[i].se + 1;
}
}
if (un_def <= r) puts("TAK");
else puts("NIE");
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
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: 0
Accepted
time: 109ms
memory: 14604kb
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:
TAK
result:
ok single line: 'TAK'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3944kb
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 #4:
score: -100
Wrong Answer
time: 83ms
memory: 12716kb
input:
1 197838 400000 34167 34169 352180 -1 235963 -1 -1 -1 160401 160405 347288 -1 270353 270354 214502 214504 183243 183245 -1 -1 -1 36193 -1 -1 -1 17557 273498 273500 269137 -1 395099 395100 285515 285518 -1 -1 71041 71042 324060 -1 -1 385151 -1 379645 -1 -1 -1 185142 -1 191584 89259 89261 328347 32834...
output:
NIE
result:
wrong answer 1st lines differ - expected: 'TAK', found: 'NIE'