Submission #897875

#TimeUsernameProblemLanguageResultExecution timeMemory
897875cadmiumskyTwo Dishes (JOI19_dishes)C++17
3 / 100
9 ms19516 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<ll,ll>; using tii = tuple<int,int,int>; // default constructorul trebuie sa fie identitate // sorry it had to be this way template<typename Mono, typename Lazy> struct AINT { const Mono ID_M = Mono(); const Lazy ID_L = Lazy(); struct Node { Mono val; Lazy lazy; Node(Mono a, Lazy b): val(a), lazy(b) {;} Node operator += (const Lazy& x) { return *this = Node(val + x, lazy + x); } Node operator + (const Node& x) const { return Node(x.val + val, Lazy()); } }; vector<Node> aint; int n, L_limit, R_limit; void init(int _n) { n = _n; L_limit = 1; R_limit = n; aint.resize(2 * n + 5, Node(ID_M, ID_L)); fill(all(aint), Node(ID_M, ID_L)); } void init(int L, int R) { n = R - L + 1; L_limit = L; R_limit = R; aint.resize(2 * n + 5, Node(ID_M, ID_L)); fill(all(aint), Node(ID_M, ID_L)); } void push(int node, int L, int R) { if(aint[node].lazy != ID_L) aint[L] += aint[node].lazy; aint[R] += aint[node].lazy; aint[node].lazy = ID_L; } tii get_sons(int node, int cl, int cr) { return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2}; } template<typename VecType> void write(const VecType& v) { write<VecType>(v, 1, 1, n); } template<typename VecType> void write(const VecType& v, int node, int cl, int cr) { if(cl == cr) { aint[node].val = v[cl]; aint[node].lazy = ID_L; return; } auto [mid, L, R] = get_sons(node, cl, cr); write(v, L, cl, mid); write(v, R, mid + 1, cr); aint[node] = aint[L] + aint[R]; return; } void set(int p, Mono val) { set(p, val, 1, L_limit, R_limit); } void set(int p, Mono val, int node, int cl, int cr) { if(cr < p || p < cl) return; if(cl == cr) { aint[node].val = val; return; } auto [mid, L, R] = get_sons(node, cl, cr); push(node, L, R); set(p, val, L, cl, mid); set(p, val, R, mid + 1, cr); aint[node] = aint[L] + aint[R]; return; } void upd(int l, int r, Lazy x) { upd(l, r, x, 1, L_limit, R_limit); } void upd(int l, int r, Lazy x, int node, int cl, int cr) { if(cr < l || r < cl) return; if(l <= cl && cr <= r) { aint[node] += x; return; } auto [mid, L, R] = get_sons(node, cl, cr); push(node, L, R); upd(l, r, x, L, cl, mid); upd(l, r, x, R, mid + 1, cr); aint[node] = aint[L] + aint[R]; return; } Mono query(int l, int r) { return query(l, r, 1, L_limit, R_limit); } Mono query(int l, int r, int node, int cl, int cr) { if(cr < l || r < cl) return ID_M; if(l <= cl && cr <= r) return aint[node].val; auto [mid, L, R] = get_sons(node, cl, cr); push(node, L, R); return query(l, r, L, cl, mid) + query(l, r, R, mid + 1, cr); } template<class CB> int find_right(CB&& cb) { return find_right(cb, 1, L_limit, R_limit); } template<class CB> int find_right(CB&& cb, int node, int cl, int cr) { if(!cb(aint[node].val, cl, cr)) return cr + 1; if(cl == cr) return cl; auto [mid, L, R] = get_sons(node, cl, cr); push(node, L, R); int tmp_rez = find_right(cb, L, cl, mid); if(tmp_rez == mid + 1) return find_right(cb, R, mid + 1, cr); return tmp_rez; } template<class CB> int find_left(CB&& cb) { return find_right(cb, 1, L_limit, R_limit); } template<class CB> int find_left(CB&& cb, int node, int cl, int cr) { if(!cb(aint[node].val, cl, cr)) return cl - 1; if(cl == cr) return cl; auto [mid, L, R] = get_sons(node, cl, cr); push(node, L, R); int tmp_rez = find_right(cb, R, mid + 1, cr); if(tmp_rez == mid) return find_right(cb, L, cl, mid); return tmp_rez; } void print(int node, int cl, int cr) { if(cl == cr) { fprintf(stderr, "(%d, %d) ", aint[node].val.simple, aint[node].val.active); return; } auto [mid, L, R] = get_sons(node, cl, cr); push(node, L, R); print(L, cl, mid); print(R, mid + 1, cr); return; } }; struct EMPT { EMPT operator +(const EMPT& x) const {return EMPT(); } bool operator != (const EMPT& x) const { return 0; } }; struct Node { ll simple; ll active; Node(): simple(0), active(0) {;} Node(ll a, ll b): simple(a), active(b) {;} Node operator +(const Node& x) const { return Node(simple + x.simple, active + x.active); } Node operator +(const EMPT& x) const { return *this; } }; const int nmax = 1e2 + 5; ll A[nmax], ALimit[nmax], AScore[nmax]; ll B[nmax], BLimit[nmax], BScore[nmax]; vector<pii> eventscol[nmax]; ll dp[nmax][nmax]; signed main() { cin.tie(0) -> sync_with_stdio(0); int n, m; cin >> n >> m; AINT<Node,EMPT> aint; aint.init(1, n); // stocam derivata s_i - s_i-1 for(int i = 1; i <= n; i++) cin >> A[i] >> ALimit[i] >> AScore[i]; for(int i = 1; i <= m; i++) cin >> B[i] >> BLimit[i] >> BScore[i]; for(int i = 1; i <= n; i++) A[i] += A[i - 1]; for(int i = 1; i <= m; i++) B[i] += B[i - 1]; //for(int i = 1; i <= n; i++) cerr << A[i] << ' '; cerr << '\n'; //for(int i = 1; i <= m; i++) cerr << B[i] << ' '; cerr << '\n'; ll _0 = 0; auto pushLineMod = [&](int ptr, int C) { auto R = aint.query(ptr, ptr); R.active += C; aint.set(ptr, R); }; auto pushColMod = [&](int ptr, int C) { auto R = aint.query(ptr, ptr); R.simple += C; aint.set(ptr, R); }; for(int i = 1; i <= n; i++) _0 += AScore[i] * (AScore[i] < 0); for(int i = 1; i <= m; i++) _0 += BScore[i] * (BScore[i] < 0); for(int i = 1; i <= n; i++) { if(ALimit[i] < A[i] || AScore[i] == 0) continue; int u = distance(B, upper_bound(B, B + m + 1, ALimit[i] - A[i])) - 1; if(AScore[i] < 0) { //cerr << i << ", " << AScore[i] << ": " << u + 1 << '\n'; eventscol[u + 1].emplace_back(i, -AScore[i]); } else { //cerr << i << ", " << AScore[i] << ": " << 0 << ' ' << u + 1 << '\n'; eventscol[0].emplace_back(i, AScore[i]); eventscol[u + 1].emplace_back(i, -AScore[i]); } } //_0 = 0; //ll inutil = 0; //{ //ll negC = 0; //for(int i = 1; i <= n; i++) //negC += (AScore[i] < 0) * AScore[i]; //for(int i = 1; i <= m; i++) //negC += (BScore[i] < 0) * BScore[i]; //for(int i = 0; i <= n; i++) { //for(int j = 0; j <= m; j++) { //if(AScore[i + 1] > 0) { //if(A[i + 1] + B[j] <= ALimit[i + 1]) //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + AScore[i + 1]); //else //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); //} //else { //if(A[i + 1] + B[j] > ALimit[i + 1]) //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - AScore[i + 1]); //else //dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); //} //if(BScore[j + 1] > 0) { //if(A[i] + B[j + 1] <= BLimit[j + 1]) //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + BScore[j + 1]); //else //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]); //} //else { //if(A[i] + B[j + 1] > BLimit[j + 1]) //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] - BScore[j + 1]); //else //dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]); //} //} //} //cerr << negC << '\n'; //for(int j = 0; j <= m; j++) { //for(int i = 1; i <= n; i++) //cout << dp[i][j] << ' '; //cout << '\t'; //for(int i = 1; i <= n; i++) //cout << dp[i][j] - dp[i - 1][j] << ' '; //cout << '\n'; //} //} //cerr << _0 << '\n'; for(int i = 0; i <= m; i++) { sort(all(eventscol[i]), [&](auto a, auto b) { return a.second < b.second; }); for(auto [ptr, C] : eventscol[i]) { if(C > 0) { int cpy = C; auto finder = [&](Node val, int cl, int cr) -> bool { if(cr <= ptr) return 0; if(val.simple > 0) return 1; return 0; }; while(1) { int nv_ptr = aint.find_right(finder); if(nv_ptr == n + 1) break; auto R = aint.query(nv_ptr, nv_ptr); int mn = min(C, R.simple); C -= mn; R.simple -= mn; aint.set(nv_ptr, R); if(C == 0) break; ptr = nv_ptr; } pushLineMod(ptr, cpy); } else pushLineMod(ptr, C), pushColMod(ptr, -C); } if(i == 0 || BScore[i] == 0 || BLimit[i] < B[i]) { _0 -= (BScore[i] < 0) * BScore[i]; //cerr << i << '\n'; //cerr << _0 << ' '; //aint.print(1, 1, n); //cerr << "\n---\n"; continue; } int u = distance(A, upper_bound(A, A + n + 1, BLimit[i] - B[i])) - 1; //cerr << B[i] << ' ' << BLimit[i] << '\n'; //cerr << i << ": " << u << ", " << BScore[i] << '\n'; //cerr << A[u] << ' ' << A[u + 1] << ' ' << BLimit[i] - B[i] << '\n'; _0 += BScore[i] * (BScore[i] > 0); //inutil += (BScore[i] > 0) * BScore[i]; if(u == n) { //cerr << i << '\n'; //cerr << _0 << ' '; //aint.print(1, 1, n); //cerr << "\n---\n"; continue; } if(BScore[i] < 0) { pushColMod(u + 1, -BScore[i]); } else { auto finder = [&](Node val, int cl, int cr) -> bool { if(cr <= u) return 0; if(val.simple > 0) return 1; return 0; }; while(1) { int nv_u = aint.find_right(finder); //cerr << nv_u << '\n'; if(nv_u == n + 1) break; auto R = aint.query(nv_u, nv_u); int mn = min(BScore[i], R.simple); BScore[i] -= mn; R.simple -= mn; aint.set(nv_u, R); if(BScore[i] == 0) break; u = nv_u; } } //cerr << i << '\n'; //cerr << _0 << ' '; //aint.print(1, 1, n); //cerr << "\n---\n"; } auto R = aint.query(1, n); //cerr << R.simple << ' ' << R.active << '\n'; cout << _0 + R.simple + R.active << '\n'; } /** Anul asta nu se da centroid -- Rugaciunile mele */

Compilation message (stderr)

dishes.cpp: In instantiation of 'tii AINT<Mono, Lazy>::get_sons(int, int, int) [with Mono = Node; Lazy = EMPT; tii = std::tuple<int, int, int>]':
dishes.cpp:125:24:   required from 'Mono AINT<Mono, Lazy>::query(int, int, int, int, int) [with Mono = Node; Lazy = EMPT]'
dishes.cpp:119:42:   required from 'Mono AINT<Mono, Lazy>::query(int, int) [with Mono = Node; Lazy = EMPT]'
dishes.cpp:232:33:   required from here
dishes.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
      |             ~~~^~~~
dishes.cpp:56:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     return {cl + cr >> 1, node + 1, node + ((cl + cr >> 1) - cl + 1) * 2};
      |                                              ~~~^~~~
#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...