Submission #97031

#TimeUsernameProblemLanguageResultExecution timeMemory
97031diamond_dukeArranging Tickets (JOI17_arranging_tickets)C++11
85 / 100
1664 ms13692 KiB
#include <algorithm> #include <cstdio> #include <vector> #include <queue> using ll = long long; int lp[200005], rp[200005], w[200005], rem[200005], n, m; ll val[200005], lazy[200005]; std::vector<int> vec[200005]; struct comp { bool operator ()(int x, int y) { return rp[x] < rp[y]; } }; inline bool check(int pos, ll cnt, ll lim) { if (cnt > lim) return false; for (int i = 0; i < n; i++) { vec[i].clear(); lazy[i] = 0; } for (int i = 0; i < m; i++) { if (lp[i] <= pos && pos < rp[i]) { vec[lp[i]].push_back(i); rem[i] = w[i]; } } std::priority_queue<int, std::vector<int>, comp> que; for (int i = 0; i <= pos; i++) { for (int x : vec[i]) que.push(x); ll cur = std::max(0ll, val[i] + cnt - lim) + 1 >> 1; while (cur && !que.empty()) { int x = que.top(); que.pop(); int sub = std::min<ll>(cur, rem[x]); cur -= sub; rem[x] -= sub; cnt -= sub << 1; lazy[lp[x]] -= sub; lazy[rp[x]] += sub << 1; if (rem[x]) que.push(x); } if (cur) return false; } for (int i = 0; i < n; i++) { if (i) lazy[i] += lazy[i - 1]; if (lazy[i] + val[i] > lim) return false; } return true; } int main() { // freopen("JOISC2017-D2T1.in", "r", stdin); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%d", lp + i, rp + i, w + i); if (lp[i] > rp[i]) std::swap(lp[i], rp[i]); val[lp[i]] += w[i]; val[rp[i]] -= w[i]; } int fir = 0, lst = 0; for (int i = 1; i < n; i++) { val[i] += val[i - 1]; if (val[i] > val[fir]) fir = i; if (val[i] == val[fir]) lst = i; } int l = 0, r = val[lst], res = -1; while (l <= r) { int mid = l + r >> 1; bool ok = false; for (int x : {fir, lst}) { for (int y = 0; y < 2; y++) ok |= check(x, val[fir] - mid + y, mid); } if (ok) { res = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", res); return 0; }

Compilation message (stderr)

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:61: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:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", lp + i, rp + i, w + 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...