제출 #1122464

#제출 시각아이디문제언어결과실행 시간메모리
1122464AnhPhamFuel Station (NOI20_fuelstation)C++20
20 / 100
123 ms7492 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define sz(r) (int)(r).size() #define all(r) (r).begin(), (r).end() const int MOD = (int)1e9 + 7; const int INF = (int)4e18 + 18; void solve(); int32_t main() { #define CODE "task" if (fopen(CODE".inp", "r")) freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout); cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false); int testcases = 1; #define multitest 0 if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); } } /** [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] **/ /** The Last Dance **/ struct FUELSTATION { int X, A, B; bool operator < (const FUELSTATION &other) const { return (X == other.X ? A < other.A : X < other.X); } }; int N, D; vector <FUELSTATION> stations; namespace sub1 { bool check_condition() { return N == 1; } void solve() { cout << (max(stations[0].X, D - stations[0].A) <= stations[0].B ? max(stations[0].X, D - stations[0].A) : D) << '\n'; } } namespace sub2 { bool check_condition() { for (auto item : stations) if (item.B != 1e9) return 0; return 1; } void solve() { sort(all(stations)); int ans = 0; int sum = 0; for (int i = 0; i < sz(stations); ++i) { ans = max(ans, stations[i].X - sum); sum += stations[i].A; } ans = max(ans, D - sum); cout << ans << '\n'; } } namespace sub356 { bool check_condition() { return N <= 1e4; } bool possible(int f) { int F = f; for (int i = 1; i < sz(stations); ++i) { f -= stations[i].X - stations[i - 1].X; if (f < 0) return 0; if (F > stations[i].B) continue; f += stations[i].A; } return 1; } void solve() { stations.push_back({ 0, 0, (int)1e9 }); stations.push_back({ D, 0, (int)1e9 }); sort(all(stations)); vector <int> max_fuel = { D }; for (auto item : stations) max_fuel.push_back(item.B); sort(all(max_fuel)); int hi = D; for (auto d : max_fuel) if (possible(d)) { hi = d; break; } int ans = -1; int lo = 0; while (lo <= hi) { int mid = (lo + hi) >> 1; if (possible(mid)) ans = mid, hi = mid - 1; else lo = mid + 1; } cout << ans << '\n'; } } namespace sub47 { const int mxN = 3e5 + 5; struct dta { int B, id; bool operator < (const dta &other) const { return B < other.B; } }; struct node { int val, lazy; } st[4 * mxN]; vector <dta> dta; vector <int> compressed_X, compressed_B; void down(int id) { int t = st[id].lazy; st[id << 1].val += t; st[id << 1 | 1].val += t; st[id << 1].lazy += t; st[id << 1 | 1].lazy += t; st[id].lazy = 0; } void build(int id, int left, int right) { if (left == right) return void(st[id].val = compressed_X[left - 1]); int mid = (left + right) >> 1; build(id << 1, left, mid); build(id << 1 | 1, mid + 1, right); st[id].val = max(st[id << 1].val, st[id << 1 | 1].val); } void update(int id, int left, int right, int l, int r, int val) { if (r < left || right < l) return; if (l <= left && right <= r) { st[id].lazy += val; st[id].val += val; return; } down(id); int mid = (left + right) >> 1; update(id << 1, left, mid, l, r, val); update(id << 1 | 1, mid + 1, right, l, r, val); st[id].val = max(st[id << 1].val, st[id << 1 | 1].val); } int get(int id, int left, int right, int pos) { if (left == right) return st[id].val; down(id); int mid = (left + right) >> 1; if (pos <= mid) return get(id << 1, left, mid, pos); return get(id << 1 | 1, mid + 1, right, pos); } vector <pair <int, int>> query; int find_ans(int f) { int mn = 1e18, sum = f; for (int i = 0; i < sz(stations); i++) if (f <= stations[i].B) query.push_back({ stations[i].X, stations[i].A }); sort(all(query)); int pre = 0; for (auto it: query) { sum = sum - (it.first - pre); mn = min(mn, sum); sum = sum + it.second; pre = it.first; } return f - mn; } void solve() { stations.push_back({ D, 0, (int)1e9 }); for (int i = 0; i < sz(stations); ++i) { dta.push_back({ stations[i].B, i }); compressed_X.push_back(stations[i].X); compressed_B.push_back(stations[i].B); } sort(all(dta)); sort(all(compressed_X)); sort(all(compressed_B)); compressed_X.erase(unique(all(compressed_X)), compressed_X.end()); compressed_B.erase(unique(all(compressed_B)), compressed_B.end()); int m = sz(compressed_X) - 1; build(1, 1, m); for (int i = 0; i < sz(stations); ++i) { int pos = lower_bound(all(compressed_X), stations[i].X) - compressed_X.begin() + 1; update(1, 1, m, pos + 1, m, -stations[i].A); } if (st[1].val <= compressed_B[0]) return void(cout << find_ans(compressed_B[0]) << '\n'); int id = 1; for (int i = 1; i < sz(compressed_B); i++) { int r = compressed_B[i - 1]; while (dta[id].B == r) { int i = dta[id].id; int pos = lower_bound(all(compressed_X), stations[i].X) - compressed_X.begin() + 1; update(1, 1, m, pos + 1, m, stations[i].A); id++; } if (st[1].val <= compressed_B[i]) return void(cout << find_ans(compressed_B[i]) << '\n'); } } } void solve() { cin >> N >> D; stations = vector <FUELSTATION> (N); for (auto &item : stations) cin >> item.X >> item.A >> item.B; if (sub1 :: check_condition()) sub1 :: solve(); else if (sub2 :: check_condition) sub2 :: solve(); else if (sub356 :: check_condition()) sub356 :: solve(); else sub47 :: solve(); }

컴파일 시 표준 에러 (stderr) 메시지

FuelStation.cpp: In function 'int32_t main()':
FuelStation.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
FuelStation.cpp:17:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen(CODE".inp", "r", stdin), freopen(CODE".out", "w", stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...