Submission #1168386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168386		MuhammadSaram	Inspector (POI13_ins)	C++20	0 / 100	1 ms	324 KiB

ins

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve()
{
	int n,m;
	cin>>n>>m;
	vector<vector<int>> st;
	for (int i=0;i<m;i++)
	{
		int t,p,j;
		cin>>t>>p>>j;
		st.push_back({t,p-1,j});
	}
	int s=0,e=m+1;
	while (s+1<e)
	{
		int mid=(s+e)/2;
		bool pos=1;
		int mn[n],mx[n]={},vl[m+2]={},a[m+1];
		for (int i=0;i<mid;i++)
		{
			a[st[i][0]]=st[i][2];
			if (!mn[st[i][1]]) mn[st[i][1]]=st[i][0];
			mn[st[i][1]]=min(mn[st[i][1]],st[i][0]);
			mx[st[i][1]]=max(mx[st[i][1]],st[i][0]);
		}
		for (int i=0;i<n;i++)
			vl[mn[i]]++,vl[mx[i]+1]--;
		for (int i=2;i<=m;i++)
			vl[i]+=vl[i-1];
		vector<pair<int,int>> v;
		for (int i=0;i<mid;i++)
		{
			if (vl[st[i][0]]-1>st[i][2] or a[st[i][0]]!=st[i][2])
				pos=0;
			v.push_back({st[i][0],st[i][2]+1});
		}
		sort(v.begin(),v.end());
		int lef=n,pre=0;
		for (auto [t,i]:v)
		{
			if (i>pre)
				lef-=i-pre;
			pre=i;
		}
		if (lef<0) pos=0;
		if (pos)
			s=mid;
		else
			e=mid;
	}
	cout<<s<<endl;
}

signed main()
{
	int t;
	cin>>t;
	while (t--)
		solve();	
	
	return 0;
}

• Subtask 1: 0 / 100