This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 1e6+2;
ll A[2][MAX], T[2][MAX], P[2][MAX];
int n[2], B[2][MAX];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n[0] >> n[1];
for(int i = 0; i < 2; i++){
A[i][0] = 0;
for(int j = 1; j <= n[i]; j++){
cin >> A[i][j] >> T[i][j] >> P[i][j-1];
A[i][j] += A[i][j-1];
}
}
for(int i = 0; i < 2; i++){
for(int j = 1; j <= n[i]; j++){
if(A[i][j] > T[i][j]) B[i][j-1] = -1;
else if(A[i][j]+A[1-i][n[1-i]] <= T[i][j]) B[i][j-1] = n[1-i];
else B[i][j-1] = (int)(upper_bound(A[1-i], A[1-i]+n[1-i], T[i][j]-A[i][j])-A[1-i]-1);
// cerr << B[i][j-1] << " ";
}
// cerr << "\n";
}
vector<vector<int>> todo(n[0]+2);
ll sum = 0;
for(int i = 0; i < n[1]; i++){
if(B[1][i] > -1) todo[B[1][i]].push_back(i), sum += P[1][i];
}
map<int, ll> s;
set<int> toCorrect;
s.emplace(0, sum);
auto correct = [&](int i){
auto it = s.find(i);
if(it == s.end() || it->second >= 0) return;
ll x = it->second;
while(true){
it = s.erase(it);
if(it == s.end()) break;
it->second += x;
if(it->second >= 0) break;
x = it->second;
}
};
auto upd = [&](int i, ll v){
s[0] += v;
s[i+1] += -v;
toCorrect.insert(0);
toCorrect.insert(i+1);
};
for(int i = 0; i < n[0]; i++){
toCorrect.clear();
if(B[0][i] > -1) upd(B[0][i], P[0][i]);
for(int j : todo[i]){
upd(j, -P[1][j]);
}
for(int j : toCorrect) correct(j);
// cerr << i << ":\n";
// for(auto [j, x] : s){
// cerr << " " << j << " " << x << "\n";
// }
}
ll ans = 0;
for(auto [i, x] : s) ans += x;
cout << ans << "\n";
}
# | 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... |