Submission #897881

#TimeUsernameProblemLanguageResultExecution timeMemory
897881cadmiumskyTwo Dishes (JOI19_dishes)C++17
74 / 100
3849 ms165036 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 = 1e6 + 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]; 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++) { 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) { if(u + 1 <= m) _0 += AScore[i], eventscol[u + 1].emplace_back(i, -AScore[i]); } else { eventscol[0].emplace_back(i, AScore[i]); eventscol[u + 1].emplace_back(i, -AScore[i]); } } 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]) { continue; } int u = distance(A, upper_bound(A, A + n + 1, BLimit[i] - B[i])) - 1; _0 += BScore[i]; if(u == 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); 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; } } } auto R = aint.query(1, 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(ll, ll, ll) [with Mono = Node; Lazy = EMPT; tii = std::tuple<long long int, long long int, long long int>; ll = long long int]':
dishes.cpp:125:24:   required from 'Mono AINT<Mono, Lazy>::query(ll, ll, ll, ll, ll) [with Mono = Node; Lazy = EMPT; ll = long long int]'
dishes.cpp:119:42:   required from 'Mono AINT<Mono, Lazy>::query(ll, ll) [with Mono = Node; Lazy = EMPT; ll = long long int]'
dishes.cpp:228: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...