제출 #366998

#제출 시각아이디문제언어결과실행 시간메모리
366998fishy15Arranging Tickets (JOI17_arranging_tickets)C++14
0 / 100
9 ms6636 KiB
#include <iostream> #include <iomanip> #include <fstream> #include <vector> #include <array> #include <algorithm> #include <utility> #include <map> #include <queue> #include <set> #include <cmath> #include <cstdio> #include <cstring> #define ll long long #define ld long double #define eps 1e-8 #define MOD 1000000007 #define INF 0x3f3f3f3f #define INFLL 0x3f3f3f3f3f3f3f3f // change if necessary #define MAXN 200010 using namespace std; int n, m; vector<array<int, 3>> range[MAXN]; ll init[MAXN]; int min_check, max_check; struct cmp { bool operator()(const array<int, 3> &a, const array<int, 3> &b) const { if (a[1] == b[1]) { if (a[0] == b[0]) { return a[2] < b[2]; } return a[0] < b[0]; } return a[1] < b[1]; } }; struct bit { ll vals[MAXN]; void reset() { memset(vals, 0, sizeof vals); for (int i = 0; i < n; i++) { ll x = init[i]; if (i) x -= init[i - 1]; upd(i, x); } } void upd(int x, ll v) { x++; while (x < MAXN) { vals[x] += v; x += x & -x; } } void upd(int l, int r, ll v) { upd(l, v); upd(r, -v); } ll qry(int x) { x++; ll res = 0; while (x) { res += vals[x]; x -= x & -x; } return res; } } b; ll check(ll m, ll n, ll t) { b.reset(); multiset<array<int, 3>, cmp> cur; for (int i = 0; i <= t; i++) { ll need_rem = (b.qry(i) + n - m + 1) / 2; n -= need_rem; for (auto &arr : range[i]) { if (arr[1] >= t) { cur.insert(arr); } } while (need_rem) { if (cur.empty()) { return false; } auto t = *cur.rbegin(); cur.erase(cur.find(t)); ll to_rem = min<ll>(t[2], need_rem); b.upd(0, t[0], to_rem); b.upd(t[0], t[1], -to_rem); b.upd(t[1], ::n, to_rem); t[2] -= to_rem; need_rem -= to_rem; if (t[2]) cur.insert(t); } } for (int i = 0; i < ::n; i++) { if (b.qry(i) > m) { return false; } } return true; } ll check(ll m) { ll a = init[min_check]; for (int i = a - m; i <= ::m; i++) { if (check(m, i, min_check) || check(m, i, max_check)) { return true; } } return false; /* return check(m, a - m, min_check) || check(m, a - m + 1, min_check) */ /* || check(m, a - m, max_check) || check(m, a - m + 1, max_check); */ } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; if (a > b) swap(a, b); init[a] += c; init[b] -= c; range[a].push_back({a, b, c}); } for (int i = 1; i < n; i++) { init[i] += init[i - 1]; } for (int i = 0; i < n; i++) { if (init[i] > init[min_check]) { min_check = i; max_check = i; } else if (init[i] == init[min_check]) { max_check = i; } } ll l = 0; ll r = init[min_check]; ll ans = init[min_check]; while (l <= r) { ll m = (l + r) / 2; if (check(m)) { ans = m; r = m - 1; } else { l = m + 1; } } cout << ans << '\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...