#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e6 + 5;
ll c1[MAXN];
ll c2[MAXN];
ll t1[MAXN];
ll t2[MAXN];
ll p1[MAXN];
ll p2[MAXN];
ll pref1[MAXN];
ll pref2[MAXN];
ll INF = 1e18;
struct d{
ll maks = 0;
ll wdol = 0;
};
ll base = 1 << 20;
d drzew[1 << 21];
ll off = 0;
struct comp{
bool operator()(const pair<int,int> &p1, const pair<int,int> &p2) const {
if(p1.first != p2.first) return p1.first < p2.first;
if(p1.second != p2.second) return p1.second > p2.second;
return false;
}
};
map<pair<int,int>, int, comp> points;
void wdol(int w){
int d = drzew[w].wdol;
drzew[2 * w].wdol += d;
drzew[2 * w].maks += d;
drzew[2 * w + 1].maks += d;
drzew[2 * w + 1].wdol += d;
drzew[w].wdol = 0;
return;
}
ll oblmax(ll w, ll a, ll b, ll akt_a, ll akt_b){
//cout << a << " " << akt_a << " " << akt_b << " " << b << " przedz\n";
if(a <= akt_a and akt_b <= b) {
return drzew[w].maks;
}
if(akt_a > b or akt_b < a) return -INF;
wdol(w);
ll mid = (akt_a + akt_b) / 2;
return max(oblmax(2 * w, a, b, akt_a, mid), oblmax(2 * w + 1, a, b, mid + 1, akt_b));
}
void ustaw(ll w, ll akt_a, ll akt_b, ll ind, ll val){
if(akt_a == akt_b){
drzew[w] = {max(drzew[w].maks, val), 0};
return;
}
wdol(w);
ll mid = (akt_a + akt_b) / 2;
if(ind <= mid){
ustaw(2 * w, akt_a, mid, ind, val);
}
else{
ustaw(2 * w + 1, mid + 1, akt_b, ind, val);
}
return;
}
void akt(ll w, ll a, ll b, ll akt_a, ll akt_b, ll val){
if(a <= akt_a and akt_b <= b){
drzew[w].maks += val;
drzew[w].wdol += val;
return;
}
if(akt_a > b or akt_b < a) return;
wdol(w);
ll mid = (akt_a + akt_b) / 2;
akt(2 * w, a, b, akt_a, mid, val);
akt(2 * w + 1, a, b, mid + 1, akt_b, val);
drzew[w].maks = max(drzew[2 * w].maks, drzew[2 * w + 1].maks);
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n, m;
cin >> n >> m;
for(ll i = 1; i < 2 * base; ++i){
drzew[i] = {0, 0};
}
for(ll i = 1; i <= n; ++i){
cin >> c1[i] >> t1[i] >> p1[i];
pref1[i] = pref1[i - 1] + c1[i];
}
for(ll i = 1; i <= m; ++i){
cin >> c2[i] >> t2[i] >> p2[i];
pref2[i] = pref2[i - 1] + c2[i];
}
for(ll i = 1; i <= n; ++i){
if(pref1[i] > t1[i]) continue;
if(pref1[i] + pref2[m] <= t1[i]){
//cout << i << " wyj\n";
off += p1[i];
continue;
}
ll p = 1;
ll k = m;
while(p != k){
ll sr = (p + k + 1) / 2;
//cout << p << " " << k << " bs1\n";
if(pref1[i] + pref2[sr] <= t1[i]){
p = sr;
}
else{
k = sr - 1;
}
}
points[{i - 1, p + 1}] += p1[i];
}
for(ll i = 1; i <= m; ++i){
if(pref2[i] > t2[i]) continue;
if(pref2[i] + pref1[n] <= t2[i]){
off += p2[i];
continue;
}
ll p = 1;
ll k = n;
while(p != k){
//cout << p << " " << k << " bs2\n";
ll sr = (p + k + 1) / 2;
if(pref2[i] + pref1[sr] <= t2[i]){
p = sr;
}
else{
k = sr - 1;
}
}
off += p2[i];
points[{p, i}] -= p2[i];
}
for(auto u : points){
ll y = u.first.second;
ll val = u.second;
ll mx = oblmax(1, 0, y - 1, 0, base - 1);
ustaw(1, 0, base - 1, y, mx);
akt(1, 0, y, 0, base, val);
}
cout << drzew[1].maks + off << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |