Submission #131598

#	Time	Username	Problem	Language	Result	Execution time	Memory
131598		youngyojun	Arranging Tickets (JOI17_arranging_tickets)	C++11	100 / 100	3362 ms	19616 KiB

arranging_tickets

#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (200005)
#define MAXM (100005)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
struct Node {
	Node(int s, int e, int c) : s(s), e(e), c(c) {}
	int s, e, c;
	bool operator < (const Node& t) const {
		if(e != t.e) return e > t.e;
		if(s != t.s) return s < t.s;
		return c > t.c;
	}
	bool operator > (const Node& t) const { return !operator <(t); }
};
 
priority_queue<Node, vector<Node>, greater<Node>> PQ;
vector<pii> G[MAXN]; // {e, c}
vector<piii> L, RL;
ll S[MAXN], Q[MAXN], V[MAXN];
int d[MAXN];
int A[MAXM], B[MAXM], C[MAXM];
int N, M;
ll Ans;
 
bool f(ll m, ll n, int x) {
	while(!PQ.empty()) PQ.pop();
	for(int i = 0; i <= x; i++) clv(G[i]);
	clv(RL);
	for(piii& l : L) {
		int s, e; tie(s, e) = l.first;
		if(x < s || e < x) continue;
		G[s].pb({e, l.second});
	}
	for(int i = 0; i < x; i++) Q[i] = (S[i] + n - m + 1) / 2;
	Q[x] = n;
	ll cnt = 0;
	for(int i = 0; i <= x; i++) {
		for(pii& v : G[i]) PQ.push(Node(i, v.first, v.second));
		while(cnt < Q[i]) {
			if(PQ.empty()) return false;
			Node ret = PQ.top(); PQ.pop();
			if(cnt+ret.c <= Q[i]) {
				RL.pb({{ret.s, ret.e}, ret.c});
				cnt += ret.c;
			} else {
				RL.pb({{ret.s, ret.e}, Q[i] - cnt});
				ll left = ret.c - Q[i] + cnt;
				PQ.push(Node(ret.s, ret.e, left));
				cnt = Q[i];
			}
		}
	}
	fill(V, V+N+1, 0);
	for(piii& l : L) {
		V[l.first.first] += l.second;
		V[l.first.second+1] -= l.second;
	}
	for(piii& l : RL) {
		int s, e, c; tie(s, e) = l.first; c = l.second;
		V[s] -= c; V[e+1] += c;
		if(s) { V[0] += c; V[s] -= c; }
		if(e+1 < N) { V[e+1] += c; V[N] -= c; }
	}
	for(int i = 1; i <= N; i++) V[i] += V[i-1];
	return (*max_element(V, V+N)) <= m;
}
bool f(vector<int>& VX, ll m) {
	for(int x : VX) {
		if(f(m, max(0ll, S[x]-m), x)) return true;
		if(f(m, max(0ll, S[x]-m+1), x)) return true;
	}
	return false;
}
ll getAns() {
	vector<int> VX;
	ll s = 1, e = *max_element(S, S+N);
	for(int i = 0; i < N; i++) if(e == S[i]) VX.pb(i);
	{
		vector<int> tmp;
		tmp.pb(VX[0]); tmp.pb(VX.back());
		sorv(tmp); univ(tmp);
		swap(VX, tmp);
	}
	for(ll m; s < e;) {
		m = (s+e)/2;
		if(f(VX, m)) e = m; else s = m+1;
	}
	return s;
}
int main() {
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
	for(int i = 0; i < M; i++) { A[i]--; B[i]--; }
	for(int i = 0; i < M; i++) {
		if(A[i] < B[i]) L.pb({{A[i], B[i]-1}, C[i]});
		else L.pb({{B[i], A[i]-1}, C[i]});
	}
	for(piii& l : L) {
		S[l.first.first] += l.second;
		S[l.first.second+1] -= l.second;
	}
	for(int i = 1; i <= N; i++) S[i] += S[i-1];
	printf("%lld\n", getAns());
	return 0;
}

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:106: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:107:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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