結果
問題 | No.631 Noelちゃんと電車旅行 |
ユーザー | T1610 |
提出日時 | 2018-01-07 19:38:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 487 ms / 2,000 ms |
コード長 | 2,418 bytes |
コンパイル時間 | 1,599 ms |
コンパイル使用メモリ | 168,164 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-02 09:33:33 |
合計ジャッジ時間 | 8,871 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 352 ms
5,248 KB |
testcase_01 | AC | 485 ms
5,248 KB |
testcase_02 | AC | 485 ms
5,248 KB |
testcase_03 | AC | 486 ms
5,248 KB |
testcase_04 | AC | 484 ms
5,248 KB |
testcase_05 | AC | 487 ms
5,248 KB |
testcase_06 | AC | 179 ms
5,248 KB |
testcase_07 | AC | 90 ms
5,248 KB |
testcase_08 | AC | 341 ms
5,248 KB |
testcase_09 | AC | 407 ms
5,248 KB |
testcase_10 | AC | 285 ms
5,248 KB |
testcase_11 | AC | 252 ms
5,248 KB |
testcase_12 | AC | 322 ms
5,248 KB |
testcase_13 | AC | 292 ms
5,248 KB |
testcase_14 | AC | 143 ms
5,248 KB |
testcase_15 | AC | 254 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,s,e) for(int i=(s); i<(int)(e); i++) #define repr(i, n) REPR(i, n, 0) #define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--) #define pb push_back #define all(r) r.begin(),r.end() #define rall(r) r.rbegin(),r.rend() #define fi first #define se second typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int INF = 1e9; const ll MOD = 1e9 + 7; double EPS = 1e-8; const int sqrtN = 350; const int MAX_N = sqrtN * sqrtN + 1; ll dat[MAX_N]; ll maxi[sqrtN]; ll lazy[sqrtN]; inline int get_i(int x) {return x / sqrtN;} inline int get_j(int x) {return x % sqrtN;} inline int get_idx(int i, int j) {return i * sqrtN + j;} inline int get_j2(int x) { int ret = x % sqrtN; if(ret == 0) return sqrtN; return ret; } void add(int l, int r, ll s) { REP(i, get_i(l), sqrtN) { int x = get_idx(i, 0), y = x + sqrtN; if(r <= x) break; if(l <= x && y <= r) { maxi[i] += s; lazy[i] += s; } else { REP(j, 0, sqrtN) { dat[get_idx(i, j)] += lazy[i]; } lazy[i] = 0; REP(j, get_j(max(x, l)), get_j2(min(y, r))) { dat[get_idx(i, j)] += s; } maxi[i] = -1e18; REP(j, 0, sqrtN) { maxi[i] = max(maxi[i], dat[get_idx(i, j)]); } } } } ll query(int l, int r) { ll ret = -1e18; REP(i, get_i(l), sqrtN) { int x = get_idx(i, 0), y = x + sqrtN; if(r <= x) break; if(l <= x && y <= r) { ret = max(ret, maxi[i]); } else { REP(j, 0, sqrtN) { dat[get_idx(i, j)] += lazy[i]; } lazy[i] = 0; REP(j, get_j(max(x, l)), get_j2(min(y, r))) { ret = max(ret, dat[get_idx(i, j)]); } } } return ret; } int main(){ int n; cin >> n; rep(i, n-1) { ll a; cin >> a; dat[i] = a + 3 * (n - i - 1); } rep(i, n) maxi[get_i(i)] = max(maxi[get_i(i)], dat[i]); int m; cin >> m; rep(i, m) { int l, r, d; cin >> l >> r >> d; --l; add(l, r, (ll)d); cout << query(0, n) << endl; } return 0; }