oj.uz

Submission #934518

# Submission time Handle Problem Language Result Execution time Memory
934518 2024-02-27T13:42:29 Z AdamGS Two Dishes (JOI19_dishes) C++17
5 / 100
 343 ms 72120 KB 
#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) continue;
    if(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]);
    upd(1, 0, N-1, 0, po-1, P[i]);
  }
  cout << cnt(1, 0, N-1, 0, m) << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 71984 KB Output is correct
2 Correct 343 ms 72120 KB Output is correct
3 Correct 151 ms 67644 KB Output is correct
4 Correct 265 ms 71228 KB Output is correct
5 Correct 8 ms 39512 KB Output is correct
6 Correct 306 ms 70956 KB Output is correct
7 Correct 67 ms 57732 KB Output is correct
8 Correct 60 ms 50004 KB Output is correct
9 Correct 150 ms 68764 KB Output is correct
10 Correct 317 ms 69136 KB Output is correct
11 Correct 111 ms 62820 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39516 KB Output is correct
2 Correct 8 ms 39516 KB Output is correct
3 Correct 9 ms 39604 KB Output is correct
4 Correct 9 ms 39516 KB Output is correct
5 Correct 9 ms 39552 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Incorrect 9 ms 39516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39516 KB Output is correct
2 Correct 8 ms 39516 KB Output is correct
3 Correct 9 ms 39604 KB Output is correct
4 Correct 9 ms 39516 KB Output is correct
5 Correct 9 ms 39552 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Incorrect 9 ms 39516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39516 KB Output is correct
2 Correct 8 ms 39516 KB Output is correct
3 Correct 9 ms 39604 KB Output is correct
4 Correct 9 ms 39516 KB Output is correct
5 Correct 9 ms 39552 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Incorrect 9 ms 39516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39516 KB Output is correct
2 Correct 8 ms 39516 KB Output is correct
3 Correct 9 ms 39604 KB Output is correct
4 Correct 9 ms 39516 KB Output is correct
5 Correct 9 ms 39552 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Incorrect 9 ms 39516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 39516 KB Output is correct
2 Correct 8 ms 39516 KB Output is correct
3 Correct 9 ms 39604 KB Output is correct
4 Correct 9 ms 39516 KB Output is correct
5 Correct 9 ms 39552 KB Output is correct
6 Correct 8 ms 39516 KB Output is correct
7 Incorrect 9 ms 39516 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 71984 KB Output is correct
2 Correct 343 ms 72120 KB Output is correct
3 Correct 151 ms 67644 KB Output is correct
4 Correct 265 ms 71228 KB Output is correct
5 Correct 8 ms 39512 KB Output is correct
6 Correct 306 ms 70956 KB Output is correct
7 Correct 67 ms 57732 KB Output is correct
8 Correct 60 ms 50004 KB Output is correct
9 Correct 150 ms 68764 KB Output is correct
10 Correct 317 ms 69136 KB Output is correct
11 Correct 111 ms 62820 KB Output is correct
12 Correct 9 ms 39516 KB Output is correct
13 Correct 8 ms 39516 KB Output is correct
14 Correct 9 ms 39604 KB Output is correct
15 Correct 9 ms 39516 KB Output is correct
16 Correct 9 ms 39552 KB Output is correct
17 Correct 8 ms 39516 KB Output is correct
18 Incorrect 9 ms 39516 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 71984 KB Output is correct
2 Correct 343 ms 72120 KB Output is correct
3 Correct 151 ms 67644 KB Output is correct
4 Correct 265 ms 71228 KB Output is correct
5 Correct 8 ms 39512 KB Output is correct
6 Correct 306 ms 70956 KB Output is correct
7 Correct 67 ms 57732 KB Output is correct
8 Correct 60 ms 50004 KB Output is correct
9 Correct 150 ms 68764 KB Output is correct
10 Correct 317 ms 69136 KB Output is correct
11 Correct 111 ms 62820 KB Output is correct
12 Correct 9 ms 39516 KB Output is correct
13 Correct 8 ms 39516 KB Output is correct
14 Correct 9 ms 39604 KB Output is correct
15 Correct 9 ms 39516 KB Output is correct
16 Correct 9 ms 39552 KB Output is correct
17 Correct 8 ms 39516 KB Output is correct
18 Incorrect 9 ms 39516 KB Output isn't correct
19 Halted 0 ms 0 KB -