oj.uz

Submission #549049

# Submission time Handle Problem Language Result Execution time Memory
549049 2022-04-15T03:32:36 Z cig32 Distributing Candies (IOI21_candies) C++17
100 / 100
 2753 ms 49432 KB 
#include "candies.h"
#include "bits/stdc++.h"
using namespace std;

#include <cassert>
#include <cstdio>
#include <vector>

struct segtree {
  struct node {
    int64_t upd = 0, mi = 0, ma = 0;
  };
  vector<node> st;
  int64_t stok;
  void push_down(int64_t idx) {
    st[2*idx+1].upd += st[idx].upd;
    st[2*idx+1].mi += st[idx].upd;
    st[2*idx+1].ma += st[idx].upd;
    st[2*idx+2].upd += st[idx].upd;
    st[2*idx+2].mi += st[idx].upd;
    st[2*idx+2].ma += st[idx].upd;
    st[idx].upd = 0;
  }
  void u(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx, int64_t val) {
    if(l <= constl && constr <= r) {
      st[idx].upd += val;
      st[idx].mi += val;
      st[idx].ma += val;
      return;
    }
    int64_t mid = (constl  +constr) >> 1;
    //almst forgot
    push_down(idx);
    if(mid <l || r <constl) u(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
    else{
      u(l, r, constl, mid, 2*idx+1, val);
      u(l, r, mid+1, constr, 2*idx+2, val);
    }
    st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi);
    st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma);
  }
  int64_t qu1(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx) {
    if(l <= constl && constr <= r) return st[idx].mi;
    int64_t mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid< l || r<constl) return qu1(l, r, mid+1, constr, 2*idx+2);
    else if(constr<l || r<mid+1) return qu1(l, r, constl, mid, 2*idx+1);
    return min(qu1(l, r, constl, mid, 2*idx+1), qu1(l, r, mid+1, constr, 2*idx+2));
  }
  int64_t qu2(int64_t l, int64_t r, int64_t constl, int64_t constr, int64_t idx) {
    if(l <= constl && constr <= r) return st[idx].ma;
    int64_t mid = (constl + constr) >> 1;
    push_down(idx);
    if(mid< l || r<constl) return qu2(l, r, mid+1, constr, 2*idx+2);
    else if(constr<l || r<mid+1) return qu2(l, r, constl, mid, 2*idx+1);
    return max(qu2(l, r, constl, mid, 2*idx+1), qu2(l, r, mid+1, constr, 2*idx+2));
  }
  public:
  void resize(int64_t k) {
    stok = k;
    st.resize(4*k + 10);
  }
  void range_add(int64_t l, int64_t r, int64_t v) {
    u(l, r, 0, stok, 0, v);
  }
  int64_t query_min(int64_t l, int64_t r) {
    return qu1(l, r, 0, stok, 0);
  }
  int64_t query_max(int64_t l, int64_t r) {
    return qu2(l, r, 0, stok, 0);
  }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  
  int n = c.size();
  std::vector<int> s(n);
  int q = l.size();
  segtree owo;
  owo.resize(q + 2);
  owo.range_add(0, 0, 1e15);
  owo.range_add(1, 1, 0);
  vector<int> in[n+1], out[n+1];
  for(int i=0; i<q; i++) {
    in[l[i]].push_back(i);
    out[r[i]+1].push_back(i);
  }
  for(int i=0; i<n; i++) {
    for(int xxxX : in[i]) {
      int x = xxxX + 2;
      int val = v[xxxX];
      owo.range_add(x, q + 1, val);
    }
    for(int xxxX: out[i]) {
      int x = xxxX + 2;
      int val = v[xxxX];
      owo.range_add(x, q + 1, -val);
    }
    int lb = 0, rb = q + 1;
    while(lb < rb) {
      int mid = (lb + rb + 1) >> 1;
      if(owo.query_max(mid, q + 1) - owo.query_min(mid, q + 1) >= c[i]) lb = mid;
      else rb = mid - 1;
    } 
    if(owo.query_max(lb, q + 1) - owo.query_min(lb, q + 1) >= c[i]) {
      if(owo.query_max(lb, q + 1) == owo.query_max(lb, lb)) {
        s[i] = owo.query_max(q + 1, q + 1) - owo.query_min(lb, q + 1);
      }
      else {
        s[i] = owo.query_max(q + 1, q + 1) - (owo.query_max(lb, q + 1) - c[i]);
      }
    }
    else {
      s[i] = owo.query_max(q + 1, q + 1);
    }
  }
  return s;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 9 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2005 ms 47480 KB Output is correct
2 Correct 2172 ms 46800 KB Output is correct
3 Correct 2236 ms 46624 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 345 ms 29756 KB Output is correct
3 Correct 864 ms 15536 KB Output is correct
4 Correct 2753 ms 48636 KB Output is correct
5 Correct 2451 ms 49024 KB Output is correct
6 Correct 1839 ms 49432 KB Output is correct
7 Correct 1788 ms 48852 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 183 ms 26024 KB Output is correct
4 Correct 577 ms 13500 KB Output is correct
5 Correct 1907 ms 40896 KB Output is correct
6 Correct 1730 ms 41624 KB Output is correct
7 Correct 1525 ms 42096 KB Output is correct
8 Correct 1918 ms 40732 KB Output is correct
9 Correct 2490 ms 42296 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 9 ms 724 KB Output is correct
6 Correct 2005 ms 47480 KB Output is correct
7 Correct 2172 ms 46800 KB Output is correct
8 Correct 2236 ms 46624 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 345 ms 29756 KB Output is correct
11 Correct 864 ms 15536 KB Output is correct
12 Correct 2753 ms 48636 KB Output is correct
13 Correct 2451 ms 49024 KB Output is correct
14 Correct 1839 ms 49432 KB Output is correct
15 Correct 1788 ms 48852 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 352 KB Output is correct
18 Correct 183 ms 26024 KB Output is correct
19 Correct 577 ms 13500 KB Output is correct
20 Correct 1907 ms 40896 KB Output is correct
21 Correct 1730 ms 41624 KB Output is correct
22 Correct 1525 ms 42096 KB Output is correct
23 Correct 1918 ms 40732 KB Output is correct
24 Correct 2490 ms 42296 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 683 ms 13604 KB Output is correct
27 Correct 337 ms 29264 KB Output is correct
28 Correct 2223 ms 47256 KB Output is correct
29 Correct 2053 ms 47660 KB Output is correct
30 Correct 1956 ms 47840 KB Output is correct
31 Correct 1934 ms 48052 KB Output is correct
32 Correct 1881 ms 48252 KB Output is correct