제출 #1066550

#제출 시각아이디문제언어결과실행 시간메모리
1066550tamthegodFish 3 (JOI24_fish3)C++17
0 / 100
2062 ms70472 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define fi first #define se second using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int maxN = 1e6 + 5; const int mod = 1e9 + 7; const ll oo = 1e18; int n, d, q; int a[maxN]; vector<pair<int, int>> query[maxN]; int sum[maxN]; int res[maxN]; void ReadInput() { cin >> n >> d; for(int i=1; i<=n; i++) { cin >> a[i]; sum[i] = sum[i - 1] + a[i]; } cin >> q; for(int i=1; i<=q; i++) { int l, r; cin >> l >> r; query[r].pb({l, i}); } } struct LazySegtree { vector<int> st, lazy; void init(int n) { st.resize(4 * n + 5, 0); lazy.resize(4 * n + 5, 0); } void down(int id, int l, int r) { int t = lazy[id]; int mid = (l + r) / 2; st[id * 2] += t * (mid - l + 1); st[id * 2 + 1] += t * (r - mid); lazy[id * 2] += t; lazy[id * 2 + 1] += t; lazy[id] = 0; } void update(int id, int l, int r, int pos, int val) { if(l > pos | r < pos) return; if(l == r && l == pos) { st[id] = val; return; } down(id, l, r); int mid = (l + r) / 2; update(id * 2, l, mid, pos, val); update(id * 2 + 1, mid + 1, r, pos, val); st[id] = st[id * 2] + st[id * 2 + 1]; } void range_upd(int id, int l, int r, int u, int v, int val) { if(l > v || r < u) return; if(l >= u && r <= v) { st[id] += val * (r - l + 1); lazy[id] += val; return; } int mid = (l + r) / 2; down(id, l, r); range_upd(id * 2, l, mid, u, v, val); range_upd(id * 2 + 1, mid + 1, r, u, v, val); st[id] = st[id * 2] + st[id * 2 + 1]; } int get(int id, int l, int r, int u, int v) { if(!u) return 0; if(l > v || r < u) return 0; if(l >= u && r <= v) return st[id]; int mid = (l + r) / 2; down(id, l, r); return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); } }; void Solve() { LazySegtree tree; tree.init(n); for(int i=1; i<=n; i++) { tree.update(1, 1, n, i, a[i]); int val = tree.get(1, 1, n, i - 1, i - 1); int j = i - 1; while(j >= 1) { int x = tree.get(1, 1, n, j, j), y = tree.get(1, 1, n, j - 1, j - 1); int v = tree.get(1, 1, n, j + 1, j + 1); int t = max(0ll, (x - v - 1) / d + 1); if(x - d < y) { tree.range_upd(1, 1, n, 1, j, -t * d); break; } else tree.update(1, 1, n, j, x - t * d); j--; } // cout << tree.get(1, 1, n, 2, 2) << " "; for(auto [l, id] : query[i]) { if(tree.get(1, 1, n, l, l) < 0) res[id] = -1; else res[id] = (sum[i] - sum[l - 1] - tree.get(1, 1, n, l, i)) / d; } } for(int i=1; i<=q; i++) cout << res[i] << '\n'; } #define taskname "sol" int32_t main() { if (fopen(taskname ".inp", "r")) { freopen(taskname ".inp", "r", stdin); //freopen(taskname ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); int T = 1; //cin >> T; for(int itest=1; itest<=T; itest++) { ReadInput(); Solve(); } }

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

Main.cpp: In member function 'void LazySegtree::update(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:57:14: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   57 |         if(l > pos | r < pos) return;
      |            ~~^~~~~
Main.cpp: In function 'void Solve()':
Main.cpp:101:13: warning: unused variable 'val' [-Wunused-variable]
  101 |         int val = tree.get(1, 1, n, i - 1, i - 1);
      |             ^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...