QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396784#2600. MismatchKevin090228🍬WA 1ms3840kbC++232.4kb2024-04-23 10:30:082024-04-23 10:30:16

Judging History

This is the latest submission verdict.

  • [2024-04-23 10:30:16]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3840kb
  • [2024-04-23 10:30:08]
  • Submitted

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