QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#396784 | #2600. Mismatch | Kevin090228🍬 | WA | 1ms | 3840kb | C++23 | 2.4kb | 2024-04-23 10:30:08 | 2024-04-23 10:30:16 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
set<int> st;
int mx1[300300],mx2[300300];
int tag[300300<<2],mn[300300<<2];
void update(int x,int l,int r,int ql,int qr,int v)
{
if(l==ql&&r==qr)
{
tag[x]+=v;
return ;
}
int mid=(l+r)/2;
if(ql<=mid)
update(x<<1,l,mid,ql,min(mid,qr),v);
if(qr>mid)
update((x<<1)|1,mid+1,r,max(mid+1,ql),qr,v);
mn[x]=min(tag[x<<1]+mn[x<<1],tag[(x<<1)|1]+mn[(x<<1)|1]);
}
vector<int> vq[300300];
int ans[300300];
int n,k;
void construct()
{
cout<<"YES\n";
vector<pii> vec;
for(int i=1;i<=n;i++)
vec.pb(mx1[i],i);
srt(vec);
for(int i=1;i<=n;i++)
ans[vec[i-1].second]=i;
for(int i=1;i<=n;i++)
cout<<ans[i]<<' ';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
st.insert(i);
vector<array<int,3>> vec;
for(int i=1;i<=k;i++)
{
int h,s,f;
cin>>h>>s>>f;
vec.push_back({h,s,f});
}
rsrt(vec);
int ind=0;
for(auto arr:vec)
{
ind++;
int s=arr[1],f=arr[2];
while(st.lower_bound(s)!=st.end()&&*st.lower_bound(s)<=f)
{
int x=*st.lower_bound(s);
if(mx1[x])
{
mx2[x]=arr[0];
st.erase(x);
}
else
{
vq[ind].pb(x);
mx1[x]=arr[0];
}
s=x+1;
}
}
for(int i=1;i<=n;i++)
update(1,1,n,i,n,-1);
for(int i=1;i<=n;i++)
update(1,1,n,max(1,mx1[i]),n,1);
for(int i=0;i<=k;i++)
{
for(auto ind:vq[i])
{
update(1,1,n,max(1,mx1[ind]),n,-1);
update(1,1,n,max(1,mx2[ind]),n,1);
}
if(mn[1]+tag[1]>=0)
{
for(auto ind:vq[i])
mx1[ind]=mx2[ind];
construct();
return 0;
}
for(auto ind:vq[i])
{
update(1,1,n,max(1,mx1[ind]),n,1);
update(1,1,n,max(1,mx2[ind]),n,-1);
}
}
cout<<"NO\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3840kb
input:
3 0 1 2
output:
YES 1 2 3
result:
wrong output format Expected integer, but "YES" found