Submission #1168402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168402		UmairAhmadMirza	Inspector (POI13_ins)	C++20	0 / 100	1467 ms	166452 KiB

ins

#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=1e5+5;
int const mod=1e9+7;

int fx[N];
int fst[N];
int lst[N];
int sn[N];
int ed[N];
vector<vector<int>> sta;
int n,m;

void solve(){
	cin>>n>>m;
	for (int i = 0; i < m; ++i)
	{
		int t,p,c;
		cin>>t>>p>>c;
		sta.push_back({t,p,c});
	}
	int low=0,high=m+1;
	while(high-low>1){
		int mid=(high+low)/2;
		for (int i = 0; i <=n; ++i){
			fst[i]=m+1;
			lst[i]=0;
		}
		for(int i=0;i<=m;i++){
			fx[i]=0;
			ed[i]=0;
			sn[i]=-1;
		}
		vector<vector<int>> tsta;
		bool ans=1;
		for (int i = 0; i < mid; ++i){
			int p=sta[i][1];
			int t=sta[i][0];
			int c=sta[i][2];
			if(sn[t]==-1)
				sn[t]=c;
			else if(sn[t]!=c)
				ans=0;
			sn[t]=c;
			fst[p]=min(fst[p],t);
			lst[p]=max(lst[p],t);
			tsta.push_back(sta[i]);
			ed[lst[p]+1]++;
		}
		for (int i = 1; i <=n; ++i)
			if(lst[i]>0){
				fx[fst[i]]++;
				fx[lst[i]+1]--;
			}
		for (int i = 1; i <=m; ++i){
			fx[i]+=fx[i-1];
			ed[i]+=ed[i-1];
		}
		sort(tsta.begin(), tsta.end());
		int curt=m;
		int ex=0;
		for(int i=mid-1;i>=0;i--){
			int t=tsta[i][0],c=tsta[i][2]+1;
			while(curt>t){
				int edh=ed[t+1]-ed[t];
				ex-=edh;
				ex=max(0,ex);
				curt--;
			}
			int edh=ed[t+1]-ed[t];
			ex-=edh;
			ex=max(0,ex);
			fx[t]+=ex;
			if(fx[t]>c || fx[t]+(ed[t]-ex)<c){
				ans=0;
				break;
			}
			ex+=(ed[t]-ex)-(c-fx[t]);
			curt--;
		}
		if(ans)
			low=mid;
		else
			high=mid;
	}
	cout<<low<<endl;

}

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

• Subtask 1: 0 / 100