Submission #708353

#TimeUsernameProblemLanguageResultExecution timeMemory
708353dooweyAnts and Sugar (JOI22_sugar)C++14
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = (int)5e5 + 10; int typ[N]; int X[N]; int A[N]; struct Node{ ll dp[2][2][3]; // [start][end][x_cnt] ll lazy_x; ll lazy_both; }; void upd(ll &a, ll b){ a = max(a, b); } Node make_node(){ Node r; for(int i = 0 ; i < 2; i ++ ){ for(int j = 0; j < 2; j ++ ){ for(int k = 0 ;k < 3; k ++ ){ r.dp[i][j][k] = -(ll)1e18; } } } r.lazy_x = 0ll; r.lazy_both = 0ll; return r; } const Node D = make_node(); ll mx[3]; Node unite(Node aa, Node bb){ Node res = aa; int cum; for(int st = 0 ; st < 2; st ++ ){ for(int en = 0; en < 2; en ++ ){ upd(res.dp[st][en][1], aa.dp[st][0][0] + bb.dp[1][en][1]); upd(res.dp[st][en][1], aa.dp[st][1][1] + bb.dp[0][en][0]); upd(res.dp[st][en][0], bb.dp[st][en][0]); for(int pi = st; pi < 3; pi ++ ){ for(int qi = max(2-pi, en); qi < 3; qi ++ ){ upd(res.dp[st][en][2], aa.dp[st][0][pi] + bb.dp[1][en][qi]); upd(res.dp[st][en][2], aa.dp[st][1][pi] + bb.dp[0][en][qi]); } upd(res.dp[st][en][pi], bb.dp[st][en][pi]); } } } return res; } Node T[N * 4 + 512]; void push(int node, int cl, int cr){ int bonus; for(int st = 0; st < 2; st ++ ){ for(int en = 0; en < 2; en ++ ){ for(int cc = 0; cc < 3; cc ++ ){ if(st == en){ bonus = st; } else{ bonus = -1; } if(bonus != -1){ if(bonus == 0) T[node].dp[st][en][cc] -= T[node].lazy_both; else T[node].dp[st][en][cc] += T[node].lazy_both; } T[node].dp[st][en][cc] += cc * 1ll * T[node].lazy_x; } } } if(cl != cr){ T[node * 2].lazy_x += T[node].lazy_x; T[node * 2 + 1].lazy_x += T[node].lazy_x; T[node * 2].lazy_both += T[node].lazy_both; T[node * 2 + 1].lazy_both += T[node].lazy_both; } T[node].lazy_x = T[node].lazy_both = 0; } void update(int node, int cl, int cr, int tl, int tr, int Xi, int Yi){ push(node, cl, cr); if(cr < tl || cl > tr) return; if(cl >= tl && cr <= tr){ if(Xi == Yi){ T[node].lazy_both = Xi; } else{ T[node].lazy_x = Xi; } push(node, cl, cr); return; } int mid = (cl + cr) / 2ll; update(node * 2, cl, mid, tl, tr, Xi, Yi); update(node * 2 + 1, mid + 1, cr, tl, tr, Xi, Yi); T[node] = unite(T[node * 2], T[node * 2 + 1]); } int k; vector<int> posi; void perform_update(int tl, int tr, int Xi, int Yi){ int ii = lower_bound(posi.begin(), posi.end(), tl) - posi.begin(); int jj = lower_bound(posi.begin(), posi.end(), tr + 1) - posi.begin(); jj -- ; //cout << ii << " " << jj << " | " << Xi << " " << Yi << "\n"; if(ii <= jj) update(1, 0, k - 1, ii, jj, Xi, Yi); } void build(int node, int cl, int cr){ T[node] = D; if(cl == cr){ T[node].dp[0][0][0] = 0; T[node].dp[0][1][1] = 0; T[node].dp[1][1][1] = 0; return; } int mid = (cl + cr) / 2; build(node * 2, cl, mid); build(node * 2 + 1, mid + 1, cr); T[node] = unite(T[node * 2], T[node * 2 + 1]); } ll get_max(){ ll V = 0ll; V = max(V, T[1].dp[0][1][1]); V = max(V, T[1].dp[0][1][2]); return V; } int main(){ fastIO; //freopen("in.txt", "r", stdin); int q, d; cin >> q >> d; for(int iq = 1; iq <= q; iq ++ ){ cin >> typ[iq] >> X[iq] >> A[iq]; posi.push_back(X[iq]); } sort(posi.begin(), posi.end()); posi.resize(unique(posi.begin(), posi.end()) - posi.begin()); k = posi.size(); build(1, 0, k - 1); ll ants = 0ll; for(int iq = 1; iq <= q; iq ++ ){ if(typ[iq] == 1){ perform_update(X[iq] + 1, (int)1e9, A[iq], A[iq]); perform_update(X[iq], X[iq], A[iq], 0); ants += A[iq]; } else{ perform_update(X[iq] + d + 1, (int)1e9, -A[iq], -A[iq]); perform_update(X[iq] - d, X[iq] + d, -A[iq], 0); } cout << ants - get_max() << "\n"; } return 0; }

Compilation message (stderr)

sugar.cpp: In function 'Node unite(Node, Node)':
sugar.cpp:49:9: warning: unused variable 'cum' [-Wunused-variable]
   49 |     int cum;
      |         ^~~
sugar.cpp: In function 'int main()':
sugar.cpp:157:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
  157 |     sort(posi.begin(), posi.end());
      |     ^~~~
      |     qsort
sugar.cpp:158:17: error: 'unique' was not declared in this scope; did you mean 'unite'?
  158 |     posi.resize(unique(posi.begin(), posi.end()) - posi.begin());
      |                 ^~~~~~
      |                 unite