Submission #206851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
206851	2020-03-05T14:32:27 Z	dennisstar	Inspector (POI13_ins)	C++17	100 / 100	972 ms	35848 KB

ins

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

int N, M;
int T[100010], J[100010], I[100010];
int mx[100010], mn[100010], A[100010];
int s[100010], e[100010];

bool ch(int X) {
	for (int i=1; i<=N; i++) mx[i]=0, mn[i]=1e9;
	for (int i=1; i<=M; i++) A[i]=s[i]=e[i]=0;
	for (int i=1; i<=X; i++) {
		if (A[T[i]]&&A[T[i]]!=I[i]+1) return 0;
		A[T[i]]=I[i]+1;
		mx[J[i]]=max(mx[J[i]], T[i]);
		mn[J[i]]=min(mn[J[i]], T[i]);
	}
	int fr=0, nfr=0, con=0, en=0, pull=0;
	for (int i=1; i<=N; i++) {
		if (mx[i]) nfr++, s[mn[i]]++, e[mx[i]]++;
		else fr++;
	}
	for (int i=1; i<=M; i++) {
		if (!A[i]) continue;
		con+=s[i]; pull-=s[i];
		if (pull<0) nfr+=pull, pull=0;
		if (A[i]>pull+con+en) nfr-=A[i]-con-en-pull, pull=A[i]-con-en;
		if (A[i]<pull+con+en) {
			if (A[i]<con) return 0;
			en=A[i]-con-pull;
			if (en<0) {
				nfr+=con+pull-A[i], fr-=con+pull-A[i];
				pull=A[i]-con, en=0;
			}
		}
		con-=e[i], en+=e[i];
	}
	return (fr>=0&&nfr+fr>=0);
}

void sol() {
	cin>>N>>M;
	for (int i=1; i<=M; i++) cin>>T[i]>>J[i]>>I[i];
	int s=1, e=M;
	while (s<e) {
		int md=(s+e+1)/2;
		if (ch(md)) s=md;
		else e=md-1;
	}
	cout<<s<<'\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int Z; cin>>Z;
	while (Z--) sol();
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	8 ms	504 KB	Output is correct
6	Correct	12 ms	632 KB	Output is correct
7	Correct	18 ms	888 KB	Output is correct
8	Correct	77 ms	3320 KB	Output is correct
9	Correct	161 ms	6520 KB	Output is correct
10	Correct	343 ms	13432 KB	Output is correct
11	Correct	468 ms	17564 KB	Output is correct
12	Correct	972 ms	35848 KB	Output is correct
13	Correct	942 ms	35064 KB	Output is correct