Submission #126551

#	Time	Username	Problem	Language	Result	Execution time	Memory
126551		ainta	Arranging Tickets (JOI17_arranging_tickets)	C++17	100 / 100	1222 ms	16952 KiB

arranging_tickets

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define SZ 262144
#define pii pair<int,int>
using namespace std;
int n, m;
vector<pii>G[201000];
long long S[201000], Z[201000], H[201000], T[201000];
int pv;
bool OK(long long K) {
	int i;
	long long s = 0;
	for (i = 0; i < n; i++) {
		H[i] = min(H[i], K);
		T[i] = 0;
	}
	H[pv] = 0;
	priority_queue<pii>PQ;
	for (i = 1; i <= pv; i++) {
		for (auto &t : G[i]) {
			if(t.first > pv)PQ.push(t);
		}
		s += H[i - 1] - H[i];
		while (s) {
			if (PQ.empty())return false;
			pii tp = PQ.top();
			PQ.pop();
			if (tp.second >= s) {
				tp.second -= s;
				T[tp.first] -= s;
				PQ.push(tp);
				s = 0;
			}
			else {
				T[tp.first] -= tp.second;
				s -= tp.second;
			}
		}
	}
	for (i = 1; i < n; i++) {
		T[i] += T[i - 1];
		if (T[i] + H[i] < 0)return false;
	}
	return true;
}
bool Pos(long long M) {
	long long i, j;
	long long bb = Z[pv] - M, ee = M / 2;
	for (i = bb; i <= bb + 1; i++) {
		for (j = 0; j < n; j++) {
			H[j] = (i + M - Z[j]) / 2;
		}
		if (H[0] < i)continue;
		if (OK(i))return true;
	}
	return false;
}
int main() {
	int i;
	//freopen("input.txt","r",stdin);
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (a > b)swap(a, b);
		G[a].push_back({ b,c });
		S[a] += c;
		S[b] -= c;
	}
	long long Mx = -1;
	pv = -1;
	for (i = 1; i < n; i++) {
		S[i] += S[i - 1];
		if (Mx < S[i]) {
			Mx = S[i];
			pv = i;
		}
	}
	for (i = 1; i <= pv; i++)Z[i] = max(Z[i - 1], S[i]);
	for (i = n - 1; i >= pv; i--)Z[i] = max(Z[i + 1], S[i]);
	long long b = 0, e = Mx - 1, mid, r = Mx;
	while (b <= e) {
		mid = (b + e) >> 1;
		if (Pos(mid)) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	printf("%lld\n", r);
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
arranging_tickets.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 35 / 35
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 15 / 15