QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #743295 | #9221. Missing Boundaries | ucup-team134# | WA | 123ms | 16204kb | C++14 | 2.3kb | 2024-11-13 18:51:56 | 2024-11-13 18:52:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int main(){
int t;
scanf("%i",&t);
while(t--){
int n,l;
scanf("%i %i",&n,&l);
int add=0;
multiset<array<int,3>> all;
for(int i=1;i<=n;i++){
int l,r;
scanf("%i %i",&l,&r);
if(l==-1 && r==-1){
add++;
}else if(l==-1){
all.insert({r,r,1});
}else if(r==-1){
all.insert({l,l,0});
}else{
all.insert({l,r,2});
}
}
vector<int> fr;
int stretch=0;
bool ok=true;
auto Work=[&](array<int,3> a,array<int,3> b){
if(a[2]==0){
if(b[2]==0 || b[2]==2){
if(b[0]<=a[0])ok=false;
else{
stretch+=b[0]-a[0]-1;
}
}else{
if(b[0]<=a[1])ok=false;
else{
stretch+=b[0]-a[1]-1;
}
}
}else if(a[2]==1 || a[2]==2){
if(b[2]==0 || b[2]==2){
if(b[0]<=a[1])ok=false;
else{
if(b[0]>a[1]+1)fr.pb(b[0]-a[1]-1);
}
}else if(b[2]==1){
if(b[1]<=a[1])ok=false;
else{
stretch+=b[1]-a[1]-1;
}
}
}
};
if(all.empty()){
Work({0,0,2},{l+1,l+1,2});
}else{
Work({0,0,2},*all.begin());
for(auto it=all.begin();next(it)!=all.end();it++){
auto a=*it;
auto b=*next(it);
Work(a,b);
}
Work(*all.rbegin(),{l+1,l+1,2});
}
if(ok){
for(int i=1;i<=add;i++){
if(fr.size()){
stretch+=fr.back()-1;
fr.pop_back();
}else{
if(stretch<=0)ok=false;
stretch--;
}
}
}
if(ok)printf("TAK\n");
else printf("NIE\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3996kb
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: 123ms
memory: 16204kb
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: 3788kb
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: 86ms
memory: 14144kb
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: 69ms
memory: 8288kb
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: -100
Wrong Answer
time: 69ms
memory: 6780kb
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 TAK
result:
wrong answer 4th lines differ - expected: 'NIE', found: 'TAK'