QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #589496 | #9221. Missing Boundaries | HJR | WA | 193ms | 22920kb | C++23 | 6.0kb | 2024-09-25 18:10:13 | 2024-09-25 18:10:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
bool ok=0;
struct node
{
int l=0,r=0;
bool operator<(const node&t)const{
if(l==t.l)
return r<t.r;
return l<t.l;
}
};//最左l 最右r
int tc=0;
void solve(){
int n,L;
cin>>n>>L;
vector<array<int,2>> a(n);
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1];
}
// if(tc==899&&ok){
// cout<<n<<" "<<L<<" ";
// for(int i=0;i<n;i++){
// cout<<a[i][0]<<" "<<a[i][1]<<" ";
// }
// }
set<node> st;
st.insert({1,L});
for(auto [x,y]:a){
if(st.empty()){
cout<<"NIE"<<endl;
return;
}
if(x!=-1&&y!=-1){
auto it=st.upper_bound({x,0x3f3f3f3f});
if(it!=st.begin()){
it=prev(it);
}
else{
cout<<"NIE"<<endl;
return;
}
int l=(*it).l;
int r=(*it).r;
if(l<=x&&r>=y){
}
else{
cout<<"NIE"<<endl;
return;
}
assert(st.count(*it));
st.erase(it);
if(x>l){
st.insert({l,x-1});
}
if(y<r){
st.insert({y+1,r});
}
}
}
set<int> vis;
map<pair<int,int>,vector<int>> mpl,mpr;
int cnt=0;
ll sum=0;
for(auto [l,r]:st){
// debug(l);
// debug(r);
sum+=r-l+1;
}
assert(sum<=L);
for(auto [x,y]:a){
if(x!=-1&&y==-1){
if(vis.count(x)){
cout<<"NIE"<<endl;
return;
}
vis.insert(x);
sum--;
if(st.empty()){
cout<<"NIE"<<endl;
return;
}
auto it=st.upper_bound({x,0x3f3f3f3f});
if(it!=st.begin()){
it=prev(it);
}
else{
cout<<"NIE"<<endl;
return;
}
assert(st.count(*it));
int l=(*it).l;
int r=(*it).r;
if(l<=x&&r>=x){
}
else{
cout<<"NIE"<<endl;
return;
}
mpl[{l,r}].push_back(x);
}
if(x==-1&&y!=-1){
if(vis.count(y)){
cout<<"NIE"<<endl;
return;
}
vis.insert(y);
sum--;
if(st.empty()){
cout<<"NIE"<<endl;
return;
}
auto it=st.upper_bound({y,0x3f3f3f3f});
if(it!=st.begin()){
it=prev(it);
}
else{
cout<<"NIE"<<endl;
return;
}
assert(st.count(*it));
int l=(*it).l;
int r=(*it).r;
if(l<=y&&r>=y){
}
else{
cout<<"NIE"<<endl;
return;
}
mpr[{l,r}].push_back(y);
}
if(x==-1&&y==-1){
sum--;
cnt++;
}
}
// for(auto [l,r]:st){
// vector<int> ml,mr;
// if(mpl.count({l,r}))
// ml=mpl[{l,r}];
// if(mpr.count({l,r}))
// mr=mpr[{l,r}];
// if(ml.size()&&mr.size()){
// sort(ml.begin(),ml.end());
// sort(mr.begin(),mr.end());
// int i=0,j=0,la=0,lar=0;
// if(ml[i]<mr[j]){
// if(ml[i]!=l)
// cnt--;
// i++;
// la=0;
// }
// else{
// lar=mr[j];
// j++;
// la=1;
// }
// while(1){
// if(j>=mr.size()&&i>=ml.size())
// break;
// if(la==0){
// if((j>mr.size()&&i<ml.size())||ml[i]<mr[j]){
// i++;
// la=0;
// }
// else{
// lar=mr[j];
// j++;
// la=1;
// }
// }
// else{
// if((j>=mr.size()&&i<ml.size())||ml[i]<mr[j]){
// if(ml[i]!=lar+1)
// cnt--;
// i++;
// la=0;
// }
// else{
// lar=mr[j];
// j++;
// la=1;
// }
// }
// }
// if(la==1&&lar!=r)
// cnt--;
// }
// else if(ml.size()){
// sort(ml.begin(),ml.end());
// if(ml[0]!=l)
// cnt--;
// }
// else if(mr.size()){
// sort(mr.begin(),mr.end());
// if(mr.back()!=r)
// cnt--;
// }
// else{
// cnt--;
// }
// }
if(cnt<0||sum<0){
cout<<"NIE"<<endl;
}
else{
cout<<"TAK"<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t;
cin>>t;
if(t==5025)
ok=1;
while(t--){
tc++;
solve();
}
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
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: 193ms
memory: 22920kb
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: 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 #4:
score: 0
Accepted
time: 148ms
memory: 20728kb
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: 101ms
memory: 11128kb
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: 76ms
memory: 7444kb
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'