Submission #985599

#TimeUsernameProblemLanguageResultExecution timeMemory
985599WhisperFish 3 (JOI24_fish3)C++17
100 / 100
466 ms60496 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define For(i, a, b) for (int i = (a); i <= (b); i++) #define Ford(i, a, b) for (int i = (b); i >= (a); i --) #define Rep(i, n) for (int i = 0; i < (n); ++i) #define Repd(i, n) for (int i = (n) - 1; i >= 0; --i) #define overload(_1, _2, _3, NAME, ...) NAME #define FOR(...) overload(__VA_ARGS__, For, Rep)(__VA_ARGS__) #define FORD(...) overload(__VA_ARGS__, Ford, Repd)(__VA_ARGS__) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void setupIO(){ #define name "Whisper" //Phu Trong from Nguyen Tat Thanh High School for gifted student srand(time(NULL)); cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); cout << fixed << setprecision(10); } template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } #define MAX 300005 int numFish, numQuery, d; int expect[MAX]; vector<pair<int, int>> event[MAX]; struct Node{ int mx, sum; Node(){ mx = -1, sum = 0; } Node(int _mx, int _sum): mx(_mx), sum(_sum){} friend Node operator + (const Node& a, const Node& b){ Node res; res.mx = max(a.mx, b.mx); res.sum = a.sum + b.sum; return res; } }; struct SegmentTree{ int n; vector<Node> st; vector<int> lz; SegmentTree(){} SegmentTree(int _n = 0){ this -> n = _n; st.resize((n << 2)); lz.resize((n << 2), -1); } void pushDown(int id, int l, int r){ if (lz[id] == -1) return; int m = (l + r) >> 1; st[id << 1].sum = (m - l + 1) * lz[id]; st[id << 1].mx = lz[id]; st[id << 1 | 1].sum = (r - m) * lz[id]; st[id << 1 | 1].mx = lz[id]; lz[id << 1] = lz[id]; lz[id << 1 | 1] = lz[id]; lz[id] = -1; } void Modify(int id, int l, int r, int u, int v, int val){ if (u > r || v < l) return; if (u <= l && v >= r) { st[id].sum = (r - l + 1) * val; st[id].mx = val; lz[id] = val; return; } int m = (l + r) >> 1; pushDown(id, l, r); Modify(id << 1, l, m, u, v, val); Modify(id << 1 | 1, m + 1, r, u, v, val); st[id] = st[id << 1] + st[id << 1 | 1]; } int Query(int id, int l, int r, int u, int v){ if (u > r || v < l) return 0; if (u <= l && v >= r) return st[id].sum; int m = (l + r) >> 1; pushDown(id, l, r); int ql = Query(id << 1, l, m, u, v); int qr = Query(id << 1 | 1, m + 1, r, u, v); return (ql + qr); } int find(int id, int l, int r, int u, int v, int x){ if (u > r || v < l) return -1; if (l == r && st[id].mx > x) return l; else if (l == r) return -1; int m = (l + r) >> 1; pushDown(id, l, r); int ans = -1; if (st[id << 1].mx > x) ans = find(id << 1, l, m, u, v, x); if (ans == -1) ans = find(id << 1 | 1, m + 1, r, u, v, x); return ans; } }; int need[MAX], dis[MAX], A[MAX]; int ans[MAX]; void Whisper(){ cin >> numFish >> d; for (int i = 1; i <= numFish; ++i) cin >> expect[i], need[i] = expect[i]; for (int i = numFish - 1; i >= 1; --i){ if (need[i] > need[i + 1]){ int diff = need[i] - need[i + 1]; diff = (diff + d - 1) / d; A[i] += diff; need[i] -= d * diff; dis[i] = diff; } } for (int i = 1; i <= numFish; ++i) A[i] += A[i - 1]; SegmentTree st(numFish + 1); cin >> numQuery; for (int i = 1; i <= numQuery; ++i){ int l, r; cin >> l >> r; event[r].emplace_back(l, i); } for (int r = 1; r <= numFish; ++r){ if (r > 1){ int id = st.find(1, 1, numFish, 1, r - 1, dis[r]); if (id == -1) id = r; if (id <= r) st.Modify(1, 1, numFish, id, r, dis[r]); } else{ st.Modify(1, 1, numFish, 1, 1, dis[1]); } for (pair<int, int>&x : event[r]){ int l = x.first, id = x.second; int num = st.Query(1, 1, numFish, l, l); if(need[l] + d * num < 0) ans[id] = -1; else{ ans[id] = A[r] - A[l - 1] - st.Query(1, 1, numFish, l, r); } } } for (int i = 1; i <= numQuery; ++i) cout << ans[i] << "\n"; } signed main(){ setupIO(); int Test = 1; // cin >> Test; for ( int i = 1 ; i <= Test ; i++ ){ Whisper(); if (i < Test) cout << '\n'; } }
#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...