結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー |
|
提出日時 | 2022-10-14 23:10:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,687 bytes |
コンパイル時間 | 2,480 ms |
コンパイル使用メモリ | 209,984 KB |
最終ジャッジ日時 | 2025-02-08 04:52:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 WA * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;ll bit[200020];ll bi2[200020];int N;ll A[200020];ll T[200020];void add(int i, ll x, int t) {while (i <= N) {if (t) {bi2[i] += x;} else {bit[i] += x;}i += (i & (-i));}}ll sum(int i, int t) {ll ret = 0;while (i) {if (t) {ret += bi2[i];} else {ret += bit[i];}i -= (i & (-i));}return ret;}void sw(int i, int t) {if (t == 0) {add(i, T[i] + A[i] - 1, 0);add(i, -1, 1);} else {add(i, 1 - A[i] - T[i], 0);add(i, 1, 1);}}int main () {cin >> N;for (int i = 1; i <= N; i ++) {cin >> A[i] >> T[i];}for (int i = 0; i <= N; i ++) {bit[i] = bi2[i] = 0;}for (int i = 1; i <= N; i ++) {add(i, A[i], 0);}int Q;cin >> Q;vector<tuple<ll, int, int, int>> X(Q);int sss = 0;for (auto& [a, b, c, d] : X) {cin >> a >> b >> c;d = sss;sss ++;}for (int i = 1; i <= N; i ++) {X.emplace_back(T[i], -1, -1, i);X.emplace_back(T[i] + A[i] - 1, -2, -1, i);}vector<ll> ans(Q);sort(X.begin(), X.end());for (auto [a, b, c, d] : X) {if (b > 0) {ans[d] = sum(c, 0) - sum(b - 1, 0);ans[d] += (sum(c, 1) - sum(b - 1, 1)) * a;} else if (b == -1) {sw(d, 0);} else {sw(d, 1);}}for (auto a : ans) {cout << a << endl;if (a < 0) {return 139;}}}