結果
問題 | No.865 24時間降水量 |
ユーザー | Shuz* |
提出日時 | 2019-08-16 22:13:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,255 bytes |
コンパイル時間 | 2,040 ms |
コンパイル使用メモリ | 181,116 KB |
実行使用メモリ | 37,760 KB |
最終ジャッジ日時 | 2024-09-22 17:17:47 |
合計ジャッジ時間 | 10,651 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
35,968 KB |
testcase_01 | AC | 12 ms
35,884 KB |
testcase_02 | AC | 13 ms
36,096 KB |
testcase_03 | AC | 12 ms
35,968 KB |
testcase_04 | AC | 13 ms
35,968 KB |
testcase_05 | AC | 23 ms
35,828 KB |
testcase_06 | AC | 22 ms
35,824 KB |
testcase_07 | AC | 22 ms
35,968 KB |
testcase_08 | AC | 23 ms
36,032 KB |
testcase_09 | AC | 23 ms
35,824 KB |
testcase_10 | AC | 82 ms
35,984 KB |
testcase_11 | AC | 83 ms
36,096 KB |
testcase_12 | AC | 82 ms
35,964 KB |
testcase_13 | AC | 83 ms
35,968 KB |
testcase_14 | AC | 82 ms
35,968 KB |
testcase_15 | TLE | - |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | AC | 12 ms
36,132 KB |
testcase_19 | AC | 12 ms
35,968 KB |
testcase_20 | AC | 12 ms
35,968 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;// Defineusing ll = long long;using ull = unsigned long long;using ld = long double;const ll dx[4] = {1, 0, -1, 0};const ll dy[4] = {0, 1, 0, -1};const ll MOD = 1e9 + 7;const ll mod = 998244353;const ll inf = 1 << 30;const ll LINF = LONG_MAX;const ll INF = 1LL << 60;const ull MAX = ULONG_MAX;#define mp make_pair#define pb push_back#define elif else if#define endl '\n'#define space ' '#define def inline auto#define func inline constexpr ll#define run(a) __attribute__((constructor)) def _##a()#define all(v) begin(v), end(v)#define rall(v) rbegin(v), rend(v)#define input(a) scanf("%lld", &(a))#define print(a) printf("%lld\n", (a))#define fi first#define se second#define ok(a, b) (0 <= (a) && (a) < (b))template <class T> using vvector = vector<vector<T>>;template <class T> using pvector = vector<pair<T, T>>;template <class T>using rpriority_queue = priority_queue<T, vector<T>, greater<T>>;template <class T> bool chmax(T &a, const T &b) {if (a < b) {a = b;return 1;}return 0;}template <class T> bool chmin(T &a, const T &b) {if (a > b) {a = b;return 1;}return 0;}// Debug#define debug(...) \{ \cerr << __LINE__ << ": " << #__VA_ARGS__ << " = "; \for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] "; \cerr << endl; \}#define dump(a, h, w) \{ \cerr << __LINE__ << ": " << #a << " = [" << endl; \rep(__i, h) { \rep(__j, w) { cerr << a[__i][__j] << space; } \cerr << endl; \} \cerr << "]" << endl; \}#define vdump(a, n) \{ \cerr << __LINE__ << ": " << #a << " = ["; \rep(__i, n) if (__i) cerr << space << a[__i]; \else cerr << a[__i]; \cerr << "]" << endl; \}// Loop#define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i)#define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i)#define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i)#define each(i, a) for (auto &&i : a)#define loop() for (;;)// Stream#define fout(n) cout << fixed << setprecision(n)#define fasten cin.tie(0), ios::sync_with_stdio(0)run(0) { fasten, fout(10); }// Speed#pragma GCC optimize("O3")#pragma GCC target("avx")// Mathfunc gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }func lcm(ll a, ll b) { return a * b / gcd(a, b); }func sign(ll a) { return a ? abs(a) / a : 0; }inline constexpr ll modulo(const ll n, const ll m = MOD) {ll k = n % m;return k + m * (k < 0);}inline constexpr ll chmod(ll &n, const ll m = MOD) {n %= m;return n += m * (n < 0);}inline constexpr ll mpow(ll a, ll n, const ll m = MOD) {ll r = 1;while (n) {if (n & 1) r *= a;chmod(r, m);a *= a;chmod(a, m);n >>= 1;}return r;}inline ll inv(const ll n, const ll m) {ll a = n, b = m, x = 1, y = 0;while (b) {ll t = a / b;a -= t * b;swap(a, b);x -= t * y;swap(x, y);}return x % m;}struct Factor {inline vector<ll> factors(ll N) {vector<ll> A;ll i = 2;while (i * i <= N) {if (N % i == 0) {A.push_back(i);N /= i;} else {i++;}}if (N != 1) A.push_back(N);sort(all(A));return A;}inline vector<ll> divisor(ll N) {vector<ll> A = factors(N), B;ll a = A.size();rep(i, 1 << a) {ll d = 1;rep(j, a) if (i & (1 << j)) d *= A[j];B.push_back(d);}sort(all(B)), B.erase(unique(all(B)), B.end());return B;}};struct csum {ll N;vector<ll> A, S;csum(vector<ll> v) : A(v), S(1) { each(k, v) S.push_back(k + S.back()); }ll sum(ll l, ll r) { return S[r] - S[l]; }ll lsum(ll r) { return S[r]; }ll rsum(ll l) { return S.back() - S[l]; }};struct RUMQ {#define INF 0#define min maxstatic const ll n = 1LL << 20;vector<ll> node, lazy, flag;RUMQ() : node(n * 2 - 1), flag(n * 2 - 1) {}inline void update(ll a, ll x, ll i = 0, ll l = 0, ll r = 1LL << 20) {if (l == a) node[i] = x;if (r - l == 1) return;if (l <= a && a < (l + r) / 2) update(a, x, i * 2 + 1, l, (l + r) / 2);if ((l + r) / 2 <= a && a < r) update(a, x, i * 2 + 2, (l + r) / 2, r);node[i] = std::min(node[i * 2 + 1], node[i * 2 + 2]);}inline ll min(ll a, ll b, ll i = 0, ll l = 0, ll r = 1LL << 20) {if (b <= l || r <= a) return INF;if (a <= l && r <= b) return node[i];return std::min(min(a, b, i * 2 + 1, l, (l + r) / 2),min(a, b, i * 2 + 2, (l + r) / 2, r));}#undef INF#undef min};signed main() {ll N;cin >> N;ll A[N], Q, T, V;RUMQ seg;rep(i, N) {cin >> A[i];rep(j, 24) seg.update(i + j, seg.max(i + j, i + j + 1) + A[i]);}cin >> Q;rep(i, Q) {cin >> T >> V;rep(j, 24) {seg.update(T + j - 1, seg.max(T + j - 1, T + j) - A[T - 1] + V);}cout << seg.max(23, N) << endl;A[T - 1] = V;}}