Submission #1217829

#TimeUsernameProblemLanguageResultExecution timeMemory
1217829baojiaopisuFish 3 (JOI24_fish3)C++20
100 / 100
948 ms60876 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using pii = pair<int, int>; using pll = pair<long long, long long>; #define pb push_back #define ins insert #define fi first #define se second #define btpc __builtin_popcount #define btclz __builtin_clz #define sz(x) (int)(x.size()); #define all(x) x.begin(), x.end() #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1}; int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1}; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int MOD = 1e9 + 7; //998244353 /* Author : Le Ngoc Bao Anh, A5K37 Le Quy Don High School for Gifted Student, Da Nang */ /* University of Wollongong */ const long long INF = 1e9; const int N = 3e5 + 10; struct SegmentTree { struct Node { ll lazy; ll sum; ll size; Node() { lazy = -1; sum = size = 0; } }; vector<Node> node; int n; SegmentTree(int _n = 0) { n = _n; node.resize(4 * n + 7); for(int i = 1; i <= 4 * n; i++) node[i] = Node(); build(1, n, 1); } void build(int l, int r, int id) { node[id].size = r - l + 1; if(l == r) return; int mid = (l + r) >> 1; build(l, mid, id << 1); build(mid + 1, r, id << 1 | 1); } void Down(int id) { if(node[id].lazy == -1) return; ll cur = node[id].lazy; node[id].lazy = -1; for(int i = (id << 1); i <= (id << 1 | 1); i++) { node[i].lazy = cur; node[i].sum = node[i].size * cur; } } Node merge(const Node &a, const Node &b) const { Node ans = Node(); ans.size = a.size + b.size; ans.sum = a.sum + b.sum; return ans; }; void update(int lo, int hi, int l, int r, int id, ll val) { if(l > hi || r < lo) return; if(lo <= l && r <= hi) { node[id].sum = node[id].size * val; node[id].lazy = val; return; } Down(id); int mid = (l + r) >> 1; update(lo, hi, l, mid, id << 1, val); update(lo, hi, mid + 1, r, id << 1 | 1, val); node[id] = merge(node[id << 1], node[id << 1 | 1]); } Node get(int lo, int hi, int l, int r, int id) { if(l > hi || r < lo) return Node(); if(lo <= l && r <= hi) return node[id]; int mid = (l + r) >> 1; Down(id); Node left = get(lo, hi, l, mid, id << 1); Node right = get(lo, hi, mid + 1, r, id << 1 | 1); return merge(left, right); } void update(int l, int r, ll x) { update(l, r, 1, n, 1, x); } ll get(int l, int r) { return get(l, r, 1, n, 1).sum; } }; ll A[N], C[N], dp[N], old[N]; ll pref[N], ans[N]; vector<pii> queries[N]; void BaoJiaoPisu() { int n; ll D; cin >> n >> D; for(int i = 1; i <= n; i++) cin >> C[i]; for(int i = 1; i <= n; i++) { A[i] = C[i] / D; old[i] = A[i]; } for(int i = 1; i < n; i++) { if(C[i] % D > C[i + 1] % D) { dp[i]++; } } for(int i = n; i >= 1; i--) { dp[i] += dp[i + 1]; A[i] += dp[i]; } int q; cin >> q; for(int i = 1; i <= q; i++) { int l, r; cin >> l >> r; queries[r].pb({l, i}); } SegmentTree IT = SegmentTree(n); for(int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + A[i]; } for(int i = 1; i <= n; i++) { int l = 1, r = i - 1, pos = i; while(l <= r) { int mid = (l + r) >> 1; if(IT.get(mid, mid) > A[i]) { pos = mid; r = mid - 1; } else { l = mid + 1; } } IT.update(pos, i, A[i]); for(auto cur : queries[i]) { int l = cur.fi; int id = cur.se; ans[id] = (pref[i] - pref[l - 1]) - IT.get(l, i); if(old[l] < A[l] - IT.get(l, l)) ans[id] = -1; } } for(int i = 1; i <= q; i++) { cout << ans[i] << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE #else //online #endif int tc = 1, ddd = 0; // cin >> tc; while(tc--) { //ddd++; //cout << "Case #" << ddd << ": "; BaoJiaoPisu(); } }
#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...