QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #581641 | #9221. Missing Boundaries | ucup-team4479# | WA | 48ms | 5216kb | C++23 | 2.1kb | 2024-09-22 13:42:08 | 2024-09-22 13:42:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m;
struct Seg
{
int l,r;
}seg[N];
int tot;
void solve()
{
cin>>n>>m;
int cnt=0;
tot=0;
for(int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
if(l==-1&&r==-1) cnt++;
else seg[++tot]={l,r};
}
if(n>m)
{
cout<<"NIE\n";
return;
}
sort(seg+1,seg+tot+1,[=](const Seg &a,const Seg &b)
{
int va=a.l==-1?a.r:a.l,vb=b.l==-1?b.r:b.l;
return va<vb;
});
int nowr=0;
long long num=m-tot;
for(int i=1;i<=tot;i++)
{
if(seg[i].l!=-1&&seg[i].r!=-1)
{
num-=seg[i].r-seg[i].l;
if(seg[i].l<=nowr)
{
cout<<"NIE\n";
return;
}
if(seg[i-1].r!=-1&&seg[i-1].r+1!=seg[i].l)
{
if(cnt<=0)
{
cout<<"NIE\n";
return;
}
num--;
cnt--;
}
nowr=seg[i].r;
}
else if(seg[i].l==-1)
{
if(seg[i].r<=nowr)
{
cout<<"NIE\n";
return;
}
nowr=seg[i].r;
}
else if(seg[i].r==-1)
{
if(seg[i].l<=nowr)
{
cout<<"NIE\n";
return;
}
nowr=seg[i].l;
}
}
if(nowr>m)
{
cout<<"NIE\n";
return;
}
if(nowr<m)
{
if(seg[tot].r!=-1)
{
if(cnt<=0)
{
cout<<"NIE\n";
}
cnt--;
}
nowr=m;
}
if(cnt>num)
{
cout<<"NIE\n";
return;
}
cout<<"TAK\n";
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T;
cin>>T;
while(T--)
solve();
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
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: 48ms
memory: 5216kb
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: 3656kb
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: 33ms
memory: 4932kb
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: 34ms
memory: 4256kb
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: 41ms
memory: 3972kb
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'