제출 #131598

#제출 시각아이디문제언어결과실행 시간메모리
131598youngyojunArranging Tickets (JOI17_arranging_tickets)C++11
100 / 100
3362 ms19616 KiB
#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; }

컴파일 시 표준 에러 (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]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...