Submission #1158500

#TimeUsernameProblemLanguageResultExecution timeMemory
1158500BolatuluCatfish Farm (IOI22_fish)C++20
100 / 100
486 ms59040 KiB
#include "fish.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("inline") #define pb push_back #define eb emplace_back #define md ((tl + tr) >> 1) #define TL v + v, tl, md #define TR v + v + 1, md + 1, tr #define all(x) (x).begin(), (x).end() #define F first #define S second using namespace std; typedef long long ll; const int N = 3e5 + 7; const ll INF = 1e18 + 7; int n, m; ll t[2][4 * N], c[2][4 * N], x[N], y[N], w[N], mx[N], dp[N]; vector <pair <int, ll>> v[N], dd[N]; int uc[2][N], u[N], T, Tc[2]; void checkc(int v, int tp) { if (uc[tp][v] < Tc[tp]) { c[tp][v] = 0; } uc[tp][v] = Tc[tp]; } void check(int v) { if (u[v] < T) { t[0][v] = t[1][v] = -INF; } u[v] = T; } ll get(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) { check(v); if (tl >= l and tr <= r) return t[tp][v]; if (tl > r or l > tr) return -INF; return max(get(tp, l, r, TL), get(tp, l, r, TR)); } ll getc(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) { checkc(v, tp); if (tl > r or l > tr or c[tp][v] == 0) return 0; if (tl >= l and tr <= r) return c[tp][v]; return getc(tp, l, r, TL) + getc(tp, l, r, TR); } void upd(int tp, int p, ll x, int v = 1, int tl = 0, int tr = n) { check(v); t[tp][v] = max(t[tp][v], x); if (tl == tr) return; if (p <= md) upd(tp, p, x, TL); else upd(tp, p, x, TR); } void updc(int tp, int p, ll x, int v = 1, int tl = 0, int tr = n) { checkc(v, tp); c[tp][v] += x; if (tl == tr) return; if (p <= md) updc(tp, p, x, TL); else updc(tp, p, x, TR); } ll max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) { n = N, m = M; bool ok = 1; ll s = 0; for (int i = 1;i <= m;i++) { x[i] = X[i - 1] + 1; if (!(x[i] & 1)) ok = 0; y[i] = Y[i - 1] + 1; w[i] = W[i - 1]; s += w[i]; dd[y[i]].eb(x[i], w[i]); } for (int i = 1;i <= n;i++) { for (auto now : dd[i]) { v[now.F].eb(i, now.S); } } if (ok) return s; vector <array <ll, 3>> vu; v[0].eb(n + 1, 0); for (int i = 1;i <= n;i++) { T = i; Tc[i & 1] = i; ll s = 0; for (auto now : v[i]) { s += now.S; updc(i & 1, now.F, now.S); } v[i].eb(n + 1, 0); sort(all(vu)); for (int j = v[i - 1].size() - 1;j >= 0;j--) { int y = v[i - 1][j].F - 1; dp[y] = -INF; } for (int j = 0;j < vu.size();j++) { if (j + 1 < vu.size() and vu[j][0] == vu[j + 1][0] and vu[j][1] == vu[j + 1][1]) continue; array <ll, 3> now = vu[j]; if (now[0] == 0) upd(0, now[1], now[2] - getc(!(i & 1), 0, now[1])); else { ll z = now[2] + getc(i & 1, 0, now[1]); dp[now[1]] = max(dp[now[1]], z); upd(1, now[1], z); } } vu.clear(); mx[i] = mx[i - 1]; int k = 0; ll ss = 0; for (int j = 0;j < v[i].size();j++) { int y = v[i][j].F - 1; while (v[i - 1][k].F <= y) { ss += v[i - 1][k].S; k++; } ll val = max(ss + get(0, 0, y), mx[i - 1]); mx[i] = max(mx[i], val); vu.pb({0, y, val}); vu.pb({1, y, val}); } for (int j = v[i].size() - 1;j >= 0;j--) { int y = v[i][j].F - 1; s -= v[i][j].S; ll val = max(get(1, y, n) - s, mx[i - 1]); mx[i] = max(mx[i], val); vu.pb({1, y, val}); } for (int j = v[i - 1].size() - 1;j >= 0;j--) { int y = v[i - 1][j].F - 1; ll val = max(dp[y], mx[i - 1]); mx[i] = max(mx[i], val); vu.pb({0, y, val}); } // cout << mx[i] << ' '; } return mx[n]; } // void solve() { // int n, m; // cin >> n >> m; // vector <int> x(m), y(m), w(m); // for (int i = 0;i < m;i++) // cin >> x[i] >> y[i] >> w[i]; // cout << max_weights(n, m, x, y, w); // } // signed main() { // solve(); // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...