QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #589365 | #9221. Missing Boundaries | HJR | WA | 441ms | 21284kb | C++23 | 5.6kb | 2024-09-25 17:29:19 | 2024-09-25 17:29:20 |
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
struct node
{
int l,r;
bool operator<(const node&t)const{
if(l==t.l)
return r<t.r;
return l<t.l;
}
};//最左l 最右r
void solve(){
int n,L;
cin>>n>>L;
vector<pair<int,int>> a(n);
for(int i=0;i<n;i++){
cin>>a[i].first>>a[i].second;
}
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--;
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){
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--;
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--;
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){
if(!mpl[{l,r}].empty()&&!mpr[{l,r}].empty()){
sort(mpl[{l,r}].begin(),mpl[{l,r}].end());
sort(mpr[{l,r}].begin(),mpr[{l,r}].end());
int i=0,j=0,la=0,lar=0;
if(mpl[{l,r}][i]<mpr[{l,r}][j]){
if(mpl[{l,r}][i]!=l)
cnt--;
i++;
la=0;
}
else{
lar=mpr[{l,r}][j];
j++;
la=1;
}
while(1){
if(j>=mpr[{l,r}].size()&&i>=mpl[{l,r}].size())
break;
if(la==0){
if((j>=mpr[{l,r}].size()&&i<mpl[{l,r}].size())||mpl[{l,r}][i]<mpr[{l,r}][j]){
i++;
la=0;
}
else{
lar=mpr[{l,r}][j];
j++;
la=1;
}
}
else{
if((j>=mpr[{l,r}].size()&&i<mpl[{l,r}].size())||mpl[{l,r}][i]<mpr[{l,r}][j]){
if(mpl[{l,r}][i]!=lar+1)
cnt--;
i++;
la=0;
}
else{
lar=mpr[{l,r}][j];
j++;
la=1;
}
}
}
if(la==1&&lar!=r)
cnt--;
}
else if(!mpl[{l,r}].empty()){
sort(mpl[{l,r}].begin(),mpl[{l,r}].end());
if(mpl[{l,r}][0]!=l)
cnt--;
}
else if(!mpr[{l,r}].empty()){
sort(mpr[{l,r}].begin(),mpr[{l,r}].end());
if(mpr[{l,r}].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;
while(t--){
solve();
}
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
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: 441ms
memory: 21284kb
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'