Submission #126505

#	Time	Username	Problem	Language	Result	Execution time	Memory
126505		ainta	Arranging Tickets (JOI17_arranging_tickets)	C++17	85 / 100	6048 ms	14540 KiB

arranging_tickets

#include<cstdio>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, m;
struct point {
	int a, b, c;
	bool operator <(point &p)const {
		return a < p.a;
	}
}w[201000];
long long S[201000], Z[201000], H[201000];
struct Tree {
	long long Mn[SZ + SZ], K[SZ + SZ];
	void UDT(int nd) {
		Mn[nd] = min(Mn[nd * 2], Mn[nd * 2 + 1]);
	}
	void init(int nd, int b, int e) {
		K[nd] = 0;
		if (b == e) {
			Mn[nd] = H[b];
			return;
		}
		int m = (b + e) >> 1;
		init(nd * 2, b, m);
		init(nd * 2 + 1, m + 1, e);
		UDT(nd);
	}
	void Add2(int nd, int x) {
		Mn[nd] += x;
		K[nd] += x;
	}
	void Spread(int nd) {
		Add2(nd * 2, K[nd]);
		Add2(nd * 2 + 1, K[nd]);
		K[nd] = 0;
	}
	void Add(int nd, int b, int e, int s, int l, int x) {
		if (s > l)return;
		if (s <= b && e <= l) {
			Add2(nd, x);
			return;
		}
		Spread(nd);
		int m = (b + e) >> 1;
		if (s <= m)Add(nd * 2, b, m, s, l, x);
		if (l > m)Add(nd * 2 + 1, m + 1, e, s, l, x);
		UDT(nd);
	}
	long long Min(int nd, int b, int e, int s, int l) {
		if (s > l)return (long long)1e18;
		if (s <= b && e <= l)return Mn[nd];
		Spread(nd);
		int m = (b + e) >> 1;
		long long r = 1e18;
		if (s <= m)r = min(Min(nd * 2, b, m, s, l), r);
		if (l > m)r = min(Min(nd * 2 + 1, m + 1, e, s, l), r);
		return r;
	}
}T;
int pv;
long long Get() {
	int i;
	T.init(1, 0, n - 1);
	long long res = 0;
	for (i = 1; i <= m; i++) {
		long long t = min(min(T.Min(1, 0, n - 1, 0, w[i].a - 1), T.Min(1, 0, n - 1, w[i].b, n - 1)), (long long)w[i].c);
		res += t;
		T.Add(1, 0, n - 1, 0, w[i].a - 1, -t);
		T.Add(1, 0, n - 1, w[i].b, n - 1, -t);
	}
	return res;
}
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 (Get() >= 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);
		w[i] = { a,b,c };
		S[a] += c;
		S[b] -= c;
	}
	sort(w + 1, w + m + 1);
	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:89: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:92: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: 0 / 15