Submission #1065500

#TimeUsernameProblemLanguageResultExecution timeMemory
1065500TobArranging Tickets (JOI17_arranging_tickets)C++14
100 / 100
1522 ms20920 KiB
#include <bits/stdc++.h> #define F first #define S second #define all(x) x.begin(), x.end() #define pb push_back #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) using namespace std; typedef long long ll; typedef pair <ll, ll> pii; const int N = 2e5 + 7; int n, m; ll a[N], l[N], r[N], c[N], ps[N]; vector <pii> iv[N]; map <ll, ll> s; bool check(int t, ll b, ll d) { if (d > b || d < 0) return 0; s.clear(); for (int i = 0; i <= n; i++) ps[i] = 0; ll cnt = 0; for (int i = 1; i <= t; i++) { ll ne = (a[i]-b+d+1)/2; for (auto it : iv[i]) if (it.F >= t) s[it.F] += it.S; while (cnt < ne) { if (s.empty()) return 0; auto p = --s.end(); ll dod = ne-cnt; if (p->S <= ne-cnt) { dod = p->S; s.erase(p); } else s[p->F] -= dod; cnt += dod; ps[0] += dod; ps[i] -= 2*dod; ps[p->F+1] += 2*dod; } } for (int i = 0; i < n; i++) { if (i) ps[i] += ps[i-1]; if (a[i] + ps[i] > b) return 0; } return 1; } int main () { FIO; cin >> n >> m; for (int i = 0; i < m; i++) { cin >> l[i] >> r[i] >> c[i]; if (l[i] > r[i]) swap(l[i], r[i]); r[i]--; a[l[i]] += c[i]; a[r[i]+1] -= c[i]; iv[l[i]].pb({r[i], c[i]}); } for (int i = 1; i < n; i++) a[i] += a[i-1]; int p = 1; for (int i = 2; i < n; i++) if (a[i] > a[p]) p = i; ll lo = 0, hi = a[p]; while (lo < hi) { ll mid = (lo + hi) / 2; int o = 0; o |= check(p, mid, a[p]-mid) | check(p, mid, a[p]-mid+1); if (o) hi = mid; else lo = mid+1; } cout << lo << "\n"; return 0; }
#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...