oj.uz

답안 #206851

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206851 2020-03-05T14:32:27 Z dennisstar Inspector (POI13_ins) C++17
100 / 100
 972 ms 35848 KB 
#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

# 결과 실행 시간 메모리 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