Submission #1065496

#TimeUsernameProblemLanguageResultExecution timeMemory
1065496TobArranging Tickets (JOI17_arranging_tickets)C++14
85 / 100
1762 ms21464 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 <int> iv[N]; multiset <int> 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 >= t) s.insert(it); while (cnt < ne) { cnt++; if (s.empty()) return 0; auto p = --s.end(); ps[0]++; ps[i] -= 2; ps[*p+1] += 2; s.erase(p); } } 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]); } 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...