Submission #846532

#TimeUsernameProblemLanguageResultExecution timeMemory
846532eltu0815Ants and Sugar (JOI22_sugar)C++14
16 / 100
537 ms163092 KiB
#include <bits/stdc++.h> #define MAX 500005 #define MOD 998244353 #define INF (ll)(1e18) #define inf (1987654321) using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef complex<long double> cpx; constexpr long double PI = acos(-1); int q; ll L; ll arr[MAX]; struct Node { int s, e; ll dp[2][2]; Node() { dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = -INF; } }; Node Merge(Node l, Node r) { Node ret = Node(); ret.s = l.s, ret.e = r.e; for(int i = 0; i <= 1; ++i) for(int j = 0; j <= 1; ++j) { for(int a = 0; a <= 1; ++a) for(int b = 0; b <= 1; ++b) { ret.dp[i][j] = max(ret.dp[i][j], l.dp[i][a] + r.dp[b][j] - (a | b) * arr[2 * l.e]); } } return ret; } Node seg[MAX << 2]; void init(int str, int ed, int node) { if(str == ed) { seg[node].s = seg[node].e = str; seg[node].dp[0][0] = seg[node].dp[1][1] = 0; seg[node].dp[0][1] = seg[node].dp[1][0] = -INF; return; } int mid = str + ed >>1; init(str, mid, node << 1); init(mid + 1, ed, node << 1 | 1); seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]); } void update(int str, int ed, int idx, int node) { if(str == ed){ seg[node].dp[1][1] = arr[2 * str - 1]; return; } int mid = str + ed >> 1; if(idx <= mid) update(str, mid, idx, node << 1); else update(mid + 1, ed, idx, node << 1 | 1); seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]); } void print(int str, int ed, int node) { cout << str << ' ' << ed << " : " << seg[node].dp[0][0] << ' ' << seg[node].dp[1][0] << ' ' << seg[node].dp[0][1] << ' ' << seg[node].dp[1][1] << endl; if(str == ed) return; int mid = str + ed >> 1; print(str, mid, node << 1); print(mid + 1, ed, node << 1 | 1); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> q >> L; init(0, q + 1 >> 1, 1); ll A = 0; for(int tt = 1; tt <= q; ++tt) { int t, x, v; cin >> t >> x >> v; arr[x] += v; if(t == 1) A += v, update(0, q + 1 >> 1, (x + 1)/2, 1); else update(0, q + 1 >> 1, x/2, 1); cout << A - max(max(seg[1].dp[0][0], seg[1].dp[0][1]), max(seg[1].dp[1][0], seg[1].dp[1][1])) << '\n'; // print(0, q/2, 1); // cout << endl; } return 0; }

Compilation message (stderr)

sugar.cpp: In function 'void init(int, int, int)':
sugar.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid = str + ed >>1;
      |               ~~~~^~~~
sugar.cpp: In function 'void update(int, int, int, int)':
sugar.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'void print(int, int, int)':
sugar.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = str + ed >> 1;
      |               ~~~~^~~~
sugar.cpp: In function 'int main()':
sugar.cpp:74:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     init(0, q + 1 >> 1, 1);
      |             ~~^~~
sugar.cpp:79:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |         if(t == 1) A += v, update(0, q + 1 >> 1, (x + 1)/2, 1);
      |                                      ~~^~~
sugar.cpp:80:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |         else update(0, q + 1 >> 1, x/2, 1);
      |                        ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...