Submission #934519

#	Time	Username	Problem	Language	Result	Execution time	Memory
934519		AdamGS	Two Dishes (JOI19_dishes)	C++17	100 / 100	3698 ms	210244 KiB

dishes

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e6+7;
ll A[LIM], S[LIM], P[LIM];
ll B[LIM], T[LIM], Q[LIM];
ll tr[4*LIM], lazy[4*LIM], N=1;
vector<ll>V[LIM];
void spl(int v) {
  lazy[2*v]+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  tr[2*v]+=lazy[v];
  tr[2*v+1]+=lazy[v];
  lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, ll x) {
  if(b<l || r<a) return;
  if(a<=l && r<=b) {
    tr[v]+=x;
    lazy[v]+=x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=max(tr[2*v], tr[2*v+1]);
}
ll cnt(int v, int l, int r, int a, int b) {
  if(b<l || r<a) return -INF;
  if(a<=l && r<=b) return tr[v];
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  return max(cnt(2*v, l, mid, a, b), cnt(2*v+1, mid+1, r, a, b));
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  while(N<=m) N*=2;
  rep(i, n) {
    cin >> A[i+1] >> S[i] >> P[i];
    A[i+1]+=A[i];
  }
  rep(i, m) {
    cin >> B[i+1] >> T[i] >> Q[i];
    B[i+1]+=B[i];
    ll po=0, ko=n+1;
    while(po<ko) {
      ll sr=(po+ko)/2;
      if(A[sr]+B[i+1]<=T[i]) po=sr+1; else ko=sr;
    }
    if(po==0) Q[i]=0;
    else V[po-1].pb(i);
  }
  ll sum=0;
  rep(i, m) sum+=Q[i];
  rep(i, m+1) tr[N+i]=sum;
  for(int i=N-1; i; --i) tr[i]=max(tr[2*i], tr[2*i+1]);
  rep(i, n) {
    sort(all(V[i]));
    for(auto j : V[i]) {
      ll a=cnt(1, 0, N-1, j+1, j+1), b=cnt(1, 0, N-1, 0, j+1);
      upd(1, 0, N-1, j+1, j+1, b-a);
    }
    ll po=0, ko=m+1;
    while(po<ko) {
      ll sr=(po+ko)/2;
      if(A[i+1]+B[sr]<=S[i]) po=sr+1; else ko=sr;
    }
    if(po!=0 && po<=m) {
      ll a=cnt(1, 0, N-1, po, po), b=cnt(1, 0, N-1, 0, po);
      upd(1, 0, N-1, po, po, b-a);
    }
    for(auto j : V[i]) upd(1, 0, N-1, 0, j, -Q[j]);
    if(po!=0) upd(1, 0, N-1, 0, po-1, P[i]);
  }
  cout << cnt(1, 0, N-1, 0, m) << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9