oj.uz

Submission #972577

# Submission time Handle Problem Language Result Execution time Memory
972577 2024-04-30T16:23:54 Z abczz Distributing Candies (IOI21_candies) C++17
100 / 100
 377 ms 59080 KB 
#include "candies.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

ll n, q;
vector <array<ll, 2>> Q[200000];
struct SegTree{
  struct Node{
    ll mx = 0;
    ll mn = 0;
    ll sum = 0;
    ll prefmx = 0;
    ll prefmn = 0;
    ll sufmx = 0;
    ll sufmn = 0;
  };
  Node st[800000];
  void merge(ll id) {
    st[id].mx = max(max(st[id*2].mx, st[id*2+1].mx), st[id*2].sufmx + st[id*2+1].prefmx);
    st[id].mn = min(min(st[id*2].mn, st[id*2+1].mn), st[id*2].sufmn + st[id*2+1].prefmn);
    st[id].sum = st[id*2].sum + st[id*2+1].sum;
    st[id].prefmx = max(st[id*2].prefmx, st[id*2].sum+st[id*2+1].prefmx);
    st[id].prefmn = min(st[id*2].prefmn, st[id*2].sum+st[id*2+1].prefmn);
    st[id].sufmx = max(st[id*2+1].sufmx, st[id*2].sufmx + st[id*2+1].sum);
    st[id].sufmn = min(st[id*2+1].sufmn, st[id*2].sufmn + st[id*2+1].sum);
  }
  void update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      st[id] = {max(0LL, w), min(0LL, w), w, max(0LL, w), min(0LL, w), max(0LL, w), min(0LL, w)};
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    merge(id);
  }
  ll query_sum(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql || ql > qr) return 0;
    else if (ql <= l && r <= qr) return st[id].sum;
    ll mid = (l+r)/2;
    return query_sum(id*2, l, mid, ql, qr) + query_sum(id*2+1, mid+1, r, ql, qr);
  }
  ll solve_mx(ll id, ll l, ll r, ll w, ll rmx) {
    if (max(st[id].mx, st[id].sufmx + rmx) <= w) return -1;
    else if (l == r) return l;
    ll mid = (l+r)/2;
    if (st[id*2+1].mx > w || st[id*2+1].sufmx + rmx > w) return solve_mx(id*2+1, mid+1, r, w, rmx);
    else return solve_mx(id*2, l, mid, w, max(rmx + st[id*2+1].sum, st[id*2+1].prefmx));
  }
  ll solve_mn(ll id, ll l, ll r, ll w, ll rmn) {
    if (min(st[id].mn, st[id].sufmn + rmn) >= w) return -1;
    else if (l == r) return l;
    ll mid = (l+r)/2;
    if (st[id*2+1].mn < w || st[id*2+1].sufmn + rmn < w) return solve_mn(id*2+1, mid+1, r, w, rmn);
    else return solve_mn(id*2, l, mid, w, min(rmn + st[id*2+1].sum, st[id*2+1].prefmn));
  }
  ll suffix_mn(ll id, ll l, ll r, ll q) {
    if (r < q) return 1e18;
    ll mid = (l+r)/2;
    if (q <= l) return st[id].sufmn;
    return min(suffix_mn(id*2, l, mid, q)+st[id*2+1].sum, suffix_mn(id*2+1, mid+1, r, q));
  }
  ll suffix_mx(ll id, ll l, ll r, ll q) {
    if (r < q) return -1e18;
    ll mid = (l+r)/2;
    if (q <= l) return st[id].sufmx;
    return max(suffix_mx(id*2, l, mid, q)+st[id*2+1].sum, suffix_mx(id*2+1, mid+1, r, q));
  }
} ST;
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  ll n = c.size(), q = l.size(), a, b, f;
  vector <int> F;
  for (int i=0; i<q; ++i) {
    Q[l[i]].push_back({i, v[i]});
    if (r[i] != n-1) Q[r[i]+1].push_back({i, 0});
  }
  for (int i=0; i<n; ++i) {
    for (auto [u, w] : Q[i]) {
      ST.update(1, 0, q-1, u, w);
    }
    a = ST.solve_mx(1, 0, q-1, c[i], 0);
    b = ST.solve_mn(1, 0, q-1, -c[i], 0);
    if (a == -1) {
      f = ST.suffix_mx(1, 0, q-1, 0);
    }
    else if (a > b) {
      f = c[i] + ST.suffix_mn(1, 0, q-1, a);
    }
    else {
      f = ST.suffix_mx(1, 0, q-1, b);
    }
    F.push_back(f);
  }
  return F;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 57040 KB Output is correct
2 Correct 342 ms 56268 KB Output is correct
3 Correct 323 ms 56272 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 196 ms 50932 KB Output is correct
3 Correct 54 ms 13748 KB Output is correct
4 Correct 338 ms 58316 KB Output is correct
5 Correct 337 ms 58828 KB Output is correct
6 Correct 377 ms 59080 KB Output is correct
7 Correct 322 ms 58488 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 82 ms 45968 KB Output is correct
4 Correct 56 ms 11920 KB Output is correct
5 Correct 144 ms 49120 KB Output is correct
6 Correct 144 ms 49852 KB Output is correct
7 Correct 160 ms 50664 KB Output is correct
8 Correct 139 ms 49080 KB Output is correct
9 Correct 135 ms 50876 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5464 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 3 ms 8028 KB Output is correct
5 Correct 3 ms 8028 KB Output is correct
6 Correct 350 ms 57040 KB Output is correct
7 Correct 342 ms 56268 KB Output is correct
8 Correct 323 ms 56272 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 196 ms 50932 KB Output is correct
11 Correct 54 ms 13748 KB Output is correct
12 Correct 338 ms 58316 KB Output is correct
13 Correct 337 ms 58828 KB Output is correct
14 Correct 377 ms 59080 KB Output is correct
15 Correct 322 ms 58488 KB Output is correct
16 Correct 2 ms 5720 KB Output is correct
17 Correct 2 ms 5724 KB Output is correct
18 Correct 82 ms 45968 KB Output is correct
19 Correct 56 ms 11920 KB Output is correct
20 Correct 144 ms 49120 KB Output is correct
21 Correct 144 ms 49852 KB Output is correct
22 Correct 160 ms 50664 KB Output is correct
23 Correct 139 ms 49080 KB Output is correct
24 Correct 135 ms 50876 KB Output is correct
25 Correct 1 ms 5724 KB Output is correct
26 Correct 53 ms 11948 KB Output is correct
27 Correct 184 ms 50768 KB Output is correct
28 Correct 319 ms 57036 KB Output is correct
29 Correct 349 ms 57288 KB Output is correct
30 Correct 339 ms 57596 KB Output is correct
31 Correct 331 ms 57804 KB Output is correct
32 Correct 336 ms 57800 KB Output is correct