QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #589504 | #9221. Missing Boundaries | HJR | WA | 248ms | 22924kb | C++23 | 5.9kb | 2024-09-25 18:12:17 | 2024-09-25 18:12:18 |
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: 3864kb
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: -100
Wrong Answer
time: 248ms
memory: 22924kb
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:
NIE
result:
wrong answer 1st lines differ - expected: 'TAK', found: 'NIE'