QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #530089 | #9221. Missing Boundaries | ucup-team1453# | AC ✓ | 230ms | 37604kb | C++14 | 1.8kb | 2024-08-24 14:51:07 | 2024-08-24 14:51:07 |
Judging History
answer
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define ull unsigned long long
#define pb emplace_back
using namespace std;
const int N = 1e6 + 7;
int n, L;
int l[N], r[N];
map<int,int>mp;
map<int,int>cov;
int win;
int a[N], b[N], c[N], tot;
void Main() {
win = 1;
mp.clear();
cov.clear();
cin >> n >> L;
mp[1] = 2;
mp[L + 1] = 1;
int num = 0;
L(i, 1, n) {
cin >> l[i] >> r[i];
if(l[i] == -1 && r[i] == -1)
++num;
if(l[i] != -1) {
if(mp[l[i]] & 1) {
win = 0;
}
mp[l[i]] |= 1;
}
if(r[i] != -1) {
++r[i];
if(mp[r[i]] & 2) {
win = 0;
}
mp[r[i]] |= 2;
}
if(l[i] != -1 && r[i] != -1) {
cov[l[i]] = 1;
}
}
L(i, 1, n) {
if(l[i] != -1 && r[i] != -1) {
auto u = mp.upper_bound(l[i]);
if(u -> first != r[i]) {
win = 0;
}
}
}
tot = 0;
for(auto&u : mp) {
++tot;
a[tot] = u.first;
b[tot] = u.second;
c[tot] = cov[a[tot]];
}
int lv = 0, rv = 0;
L(i, 1, tot - 1) if(!c[i]) {
int lp = b[i] & 1;
int rp = b[i + 1] >> 1 & 1;
if(!lp && !rp) {
lv += 1;
rv += a[i + 1] - a[i];
} else if(lp && rp) {
if(a[i + 1] - a[i] == 1) {
win = 0;
} else {
rv += a[i + 1] - a[i] - 2;
}
} else {
rv += a[i + 1] - a[i] - 1;
}
}
// cout << lv << ' ' << num << ' ' << rv << '\n';
if(lv <= num && num <= rv && win) {
cout << "TAK\n";
} else {
cout << "NIE\n";
}
}
int main() {
// freopen("data.txt","r",stdin);
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin >> t; while(t--) Main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11924kb
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: 167ms
memory: 32660kb
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: 2ms
memory: 11852kb
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: 0
Accepted
time: 150ms
memory: 35524kb
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:
TAK
result:
ok single line: 'TAK'
Test #5:
score: 0
Accepted
time: 116ms
memory: 22948kb
input:
2 97340 150000 -1 101927 105937 -1 -1 107253 -1 47307 110550 -1 84061 84062 125176 125177 -1 15915 29617 -1 -1 -1 -1 43147 115958 -1 101807 101808 24866 -1 66826 66828 -1 31640 -1 5610 1281 1284 -1 -1 -1 -1 -1 73973 -1 2945 29064 -1 30653 -1 -1 63714 -1 -1 141389 141390 -1 27465 57358 -1 47388 47389...
output:
NIE NIE
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 92ms
memory: 17620kb
input:
4 50000 50000 11702 -1 -1 3148 30364 -1 48876 -1 -1 10739 -1 44459 11634 -1 39348 -1 38829 -1 16182 -1 37933 -1 35295 -1 43280 -1 37745 -1 -1 40076 358 -1 14043 -1 13975 -1 41942 -1 -1 13182 14780 -1 -1 14663 3998 -1 -1 24474 -1 6583 -1 9620 -1 37944 12103 -1 8307 -1 45760 -1 -1 2924 25441 -1 -1 194...
output:
TAK NIE NIE NIE
result:
ok 4 lines
Test #7:
score: 0
Accepted
time: 165ms
memory: 29408kb
input:
1 197884 400000 299276 299281 340251 -1 -1 350350 315166 -1 103436 103438 164740 164742 237539 -1 383864 -1 205194 -1 -1 -1 69029 69030 -1 -1 231837 231838 35835 35837 387743 -1 125024 -1 -1 -1 -1 -1 -1 -1 -1 283202 94212 94213 219223 219224 -1 -1 -1 139549 260062 -1 387170 387173 -1 328548 -1 -1 -1...
output:
NIE
result:
ok single line: 'NIE'
Test #8:
score: 0
Accepted
time: 119ms
memory: 19060kb
input:
2 97399 150000 -1 -1 97327 97328 94010 94011 72148 -1 -1 28604 -1 -1 139279 -1 -1 -1 67725 67726 93094 -1 -1 10828 37742 -1 69460 -1 -1 -1 -1 -1 80200 80202 126739 -1 131808 131810 -1 13390 -1 -1 141120 141121 127549 -1 -1 -1 -1 -1 66081 -1 100916 100918 -1 -1 25966 -1 47034 47036 101842 -1 -1 -1 -1...
output:
NIE NIE
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 96ms
memory: 17592kb
input:
4 50000 1000000000 218423429 -1 593054951 -1 345188314 -1 839833278 -1 -1 253444951 -1 532444671 -1 866445317 -1 476576639 -1 950754898 -1 735671066 71213664 -1 -1 363816338 -1 451093114 487349837 -1 -1 987865563 672130428 -1 -1 313206174 -1 311825154 -1 209018142 836501057 -1 -1 387134322 -1 939803...
output:
NIE NIE TAK NIE
result:
ok 4 lines
Test #10:
score: 0
Accepted
time: 117ms
memory: 23188kb
input:
2 97206 150000 41741 41742 -1 -1 29609 29610 -1 -1 94303 94305 67375 -1 84593 84597 -1 -1 97516 97517 -1 -1 110718 -1 129532 129533 -1 74454 -1 145160 118122 -1 -1 -1 -1 131430 -1 -1 77307 -1 -1 -1 35606 35607 -1 -1 77284 77286 84225 -1 82910 82911 55414 55418 -1 145197 -1 -1 -1 41997 41620 41621 16...
output:
NIE NIE
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 122ms
memory: 26572kb
input:
1 200000 1000000000 -1 -1 709526131 709534689 820094363 820094954 -1 558894593 253939639 253940489 755238142 -1 356834271 -1 720874328 -1 -1 797706622 -1 -1 877671011 877674221 9379767 9379808 152611373 -1 -1 584054839 -1 28003439 137254045 -1 -1 -1 -1 -1 -1 371861650 -1 -1 898245136 -1 610262985 61...
output:
TAK
result:
ok single line: 'TAK'
Test #12:
score: 0
Accepted
time: 46ms
memory: 11832kb
input:
30000 6 9 -1 -1 -1 5 7 8 -1 2 -1 -1 3 -1 8 10 -1 -1 2 4 8 -1 -1 -1 3 6 2 10 -1 -1 -1 -1 5 10 7 -1 7 -1 -1 -1 -1 -1 -1 10 5 7 4 5 -1 -1 4 -1 -1 7 -1 4 9 10 -1 -1 -1 -1 8 9 9 -1 5 -1 -1 -1 -1 2 4 9 3 7 3 5 5 -1 3 3 -1 3 10 10 5 -1 1 3 -1 6 4 7 -1 5 2 -1 6 8 -1 9 7 -1 2 -1 1 6 3 -1 9 9 5 8 -1 4 1 3 8 9...
output:
TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE NIE TAK TAK TAK NIE NIE NIE NIE NIE NIE NIE TAK TAK NIE TAK NIE NIE NIE TAK NIE NIE NIE NIE NIE TAK NIE NIE NIE NIE NIE NIE TAK TAK NIE NIE NIE NIE NIE NIE TAK NIE TAK NIE NIE NIE NIE TAK NIE TAK NIE NIE TAK TAK NIE NIE TAK TAK NIE ...
result:
ok 30000 lines
Test #13:
score: 0
Accepted
time: 96ms
memory: 26728kb
input:
1 195372 260000 -1 -1 -1 -1 -1 -1 -1 -1 215077 215079 -1 -1 141747 141748 219215 219217 -1 -1 214597 -1 -1 -1 -1 12308 -1 239294 -1 -1 -1 122072 -1 -1 197185 197186 21277 -1 231532 231533 -1 44577 216395 216400 -1 -1 199359 199362 -1 -1 186138 -1 186390 -1 -1 -1 -1 -1 9302 9303 -1 -1 245140 245142 -...
output:
TAK
result:
ok single line: 'TAK'
Test #14:
score: 0
Accepted
time: 120ms
memory: 23268kb
input:
2 97365 150000 -1 27726 -1 87782 32929 32931 -1 64034 -1 92712 -1 121389 22208 -1 67003 -1 45846 45849 -1 121826 -1 -1 -1 88928 -1 -1 -1 -1 143878 143879 -1 29980 66219 66221 -1 142885 97733 -1 7852 7855 101823 -1 57332 57333 40274 40275 136730 -1 -1 -1 147601 147603 83568 83569 -1 121072 126102 126...
output:
NIE NIE
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 225ms
memory: 16808kb
input:
4 50000 1000000000 885955908 885956029 50702541 50730841 814888309 814937371 414548674 414571477 861819623 861834659 966697796 966749971 518247844 518250200 368013240 368013498 779106289 779156153 477602975 477606428 294865157 294875803 428298345 428311021 867052988 867058798 883883673 883912864 561...
output:
TAK NIE NIE NIE
result:
ok 4 lines
Test #16:
score: 0
Accepted
time: 163ms
memory: 32752kb
input:
1 200000 1000000000 -1 710939853 -1 488938179 349393926 -1 846794794 -1 -1 694470074 -1 365852741 -1 135624850 178370367 -1 290864243 290868406 -1 480771847 78595105 -1 487426291 487431007 786738388 -1 -1 994025836 657743521 -1 -1 570501502 -1 78293205 -1 181934315 992984484 992998639 720015162 7200...
output:
NIE
result:
ok single line: 'NIE'
Test #17:
score: 0
Accepted
time: 145ms
memory: 18784kb
input:
5025 2 18 1 6 7 18 13 13 2 -1 -1 1 -1 3 4 4 5 -1 10 -1 7 -1 11 -1 -1 6 -1 9 13 13 8 8 12 12 5 25 -1 10 19 23 -1 15 -1 -1 24 25 19 21 -1 7 6 -1 17 -1 -1 4 -1 -1 11 -1 -1 -1 -1 15 -1 10 -1 16 21 21 -1 -1 -1 5 2 2 3 3 -1 19 -1 14 8 8 1 -1 11 28 -1 -1 -1 17 19 -1 -1 -1 13 14 -1 18 -1 -1 -1 -1 27 28 -1 -...
output:
TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK TAK ...
result:
ok 5025 lines
Test #18:
score: 0
Accepted
time: 148ms
memory: 36168kb
input:
1 200000 1000000000 -1 695759160 61270148 61270687 554889654 -1 -1 -1 163412608 -1 278745598 278748206 480245270 -1 -1 -1 -1 465564952 -1 -1 36331045 -1 690762941 690767208 56107619 -1 -1 568728079 -1 871992979 -1 -1 428704395 428711065 740938473 740946716 -1 -1 -1 572572816 179863138 -1 -1 -1 -1 -1...
output:
NIE
result:
ok single line: 'NIE'
Test #19:
score: 0
Accepted
time: 144ms
memory: 16684kb
input:
5062 17 18 12 -1 -1 -1 2 2 10 10 13 -1 14 -1 -1 -1 3 -1 4 -1 1 -1 9 9 -1 7 -1 5 3 3 -1 11 -1 -1 18 18 2 8 7 8 1 7 4 18 16 -1 17 17 7 -1 1 6 10 30 6 25 25 -1 -1 5 -1 7 -1 21 1 -1 -1 12 22 -1 13 -1 29 30 1 28 1 28 4 11 10 11 -1 -1 8 9 -1 8 14 24 14 14 4 -1 10 -1 23 -1 20 -1 -1 18 15 -1 21 22 24 24 12 ...
output:
NIE NIE NIE NIE TAK NIE NIE NIE TAK TAK NIE NIE NIE TAK NIE TAK NIE NIE NIE NIE NIE TAK TAK TAK NIE NIE TAK NIE TAK NIE NIE TAK NIE NIE TAK NIE NIE NIE NIE NIE TAK TAK NIE NIE NIE TAK TAK NIE NIE NIE TAK TAK NIE NIE NIE NIE NIE NIE NIE TAK NIE TAK NIE NIE NIE NIE NIE NIE NIE NIE NIE TAK TAK TAK NIE ...
result:
ok 5062 lines
Test #20:
score: 0
Accepted
time: 153ms
memory: 37604kb
input:
1 197917 400000 -1 186043 -1 393764 -1 209151 -1 232834 152642 -1 128323 128324 -1 138647 -1 79698 59539 -1 365378 365379 359496 359497 344007 344010 174369 174371 93559 -1 -1 262203 32162 -1 280199 280200 194386 -1 396219 396220 -1 165258 -1 -1 -1 73372 178854 178856 241466 -1 138179 138181 -1 8385...
output:
TAK
result:
ok single line: 'TAK'
Test #21:
score: 0
Accepted
time: 116ms
memory: 19196kb
input:
2 97113 150000 63160 63161 -1 -1 87838 -1 -1 -1 -1 -1 -1 87939 124087 124091 -1 -1 -1 -1 127065 127068 -1 15861 -1 41210 145016 -1 149702 149703 100217 -1 11178 -1 90641 90644 -1 -1 137489 -1 19633 -1 -1 62518 137384 -1 118201 -1 5417 -1 129248 -1 -1 -1 -1 71305 65722 65725 -1 145580 -1 32416 -1 145...
output:
NIE NIE
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 230ms
memory: 18840kb
input:
4 50000 1000000000 196912598 196915922 45351610 45396286 42940984 42959715 584469269 584477019 393039448 393047100 437516233 437519175 442129337 442141150 924579436 924596732 125455800 125489225 663041726 663081484 466494019 466509761 658297840 658316558 666132418 666148132 311508671 311509270 93140...
output:
NIE NIE TAK NIE
result:
ok 4 lines
Test #23:
score: 0
Accepted
time: 97ms
memory: 22644kb
input:
1 195117 260000 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 43637 132553 132554 54001 -1 -1 -1 -1 45188 -1 -1 148978 148979 -1 -1 -1 -1 157922 -1 -1 -1 -1 -1 -1 225251 -1 -1 54563 -1 90729 90730 84435 -1 -1 86766 -1 91723 3278 -1 75544 -1 -1 -1 -1 215060 123806 123807 -1 -1 230929 -1 -1 -1 -1 -1 -1 62020 -1 -1...
output:
NIE
result:
ok single line: 'NIE'
Test #24:
score: 0
Accepted
time: 114ms
memory: 15520kb
input:
4 50000 1000000000 -1 195101318 818192684 818204368 -1 119947219 936829311 -1 303789819 -1 -1 171041521 -1 -1 769256934 769264518 -1 -1 -1 993993029 795806219 -1 549944487 -1 -1 -1 622597720 -1 -1 988155574 679878225 -1 -1 824917887 -1 475000374 581286760 581298816 -1 -1 461053775 -1 -1 615600639 64...
output:
NIE TAK NIE NIE
result:
ok 4 lines
Test #25:
score: 0
Accepted
time: 86ms
memory: 30832kb
input:
1 195461 260000 102851 -1 -1 132821 -1 -1 -1 -1 -1 -1 -1 -1 -1 24015 85541 85543 -1 -1 -1 -1 198562 -1 -1 192504 -1 41115 -1 -1 22171 22172 -1 92869 -1 -1 -1 -1 93810 93813 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 247413 20115 -1 -1 40272 -1 -1 -1 44226 -1 -1 37476 -1 121698 121700 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
TAK
result:
ok single line: 'TAK'
Test #26:
score: 0
Accepted
time: 218ms
memory: 18796kb
input:
4 49930 1000000000 265059427 265078443 120159781 120175880 645427935 645433360 458514133 458525664 594158536 594170877 221369142 221373319 501756273 501764692 820342165 820395256 684615212 684622057 887102718 887107268 987456588 987476580 240154482 240168575 449562089 449571987 954156145 954159491 7...
output:
NIE NIE NIE TAK
result:
ok 4 lines
Extra Test:
score: 0
Extra Test Passed