oj.uz

Submission #436549

# Submission time Handle Problem Language Result Execution time Memory
436549 2021-06-24T15:29:25 Z monsoon Distributing Candies (IOI21_candies) C++17
67 / 100
 520 ms 13516 KB 
#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long ll;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  int n = c.size(), q = v.size();
  vector<int> a(n);

  int sub_1 = n <= 2000 && q <= 2000;
  int sub_2 = 1;
  REP(i,q) if (v[i] < 0) sub_2 = 0;
  int sub_3 = *min_element(c.begin(),c.end()) == *max_element(c.begin(),c.end());
  int sub_4 = 1;
  REP(i,q) if (l[i] != 0 || r[i] != n-1) sub_4 = 0;

  if (sub_1) {

    REP(i,q) {
      for (int j = l[i]; j <= r[i]; ++j) {
        a[j] += v[i];
        a[j] = max(0, min(c[j], a[j]));
      }
    }

  } else if (sub_2) {

    int base = 1;
    while (base < n) base *= 2;

    vector<ll> tree(2*base);

    auto add = [&](int xl, int xr, int v) {
      xl += base;
      xr += base;
      tree[xl] += v;
      if (xl == xr) return;
      tree[xr] += v;
      while (xl/2 != xr/2) {
        if (~xl&1) tree[xl+1] += v;
        if (xr&1) tree[xr-1] += v;
        xl /= 2;
        xr /= 2;
      }
    };

    REP(i,q) {
      add(l[i], r[i], v[i]);
    }

    REP(i,base) {
      tree[2*i] += tree[i];
      tree[2*i+1] += tree[i];
    }

    REP(i,n) {
      a[i] = min(tree[base+i], ll(c[i]));
    }

  } else if (sub_3) {
    const int C = c[0];
    int base = 1;
    while (base < n) base *= 2;

    struct info {
      int x1, y1, y2;
      info(int x1, int y1, int y2) : x1(x1), y1(y1), y2(y2) { }

      int get_y(int x) const {
        int x2 = x1 + y2 - y1;
        if (x <= x1) return y1;
        if (x >= x2) return y2;
        return x - x1 + y1;
      }
    };

    auto merge = [&](const info& G, const info& F) {
      // G( F(x) )
      int y1 = G.get_y(F.y1), y2 = G.get_y(F.y2);
      int x1 = y1 == y2 ? 0 : F.x1 + max(0, G.x1 - F.y1);
      return info{ x1, y1, y2 };
    };

    auto single = [&](int val) {
      int v = min(abs(val), C);
      if (val >= 0) return info{ 0, v, C };
      else return info{ v, 0, C-v };
    };

    vector<info> tree(2*base, info{ 0, 0, C });

    auto push = [&](int no) {
      tree[2*no] = merge(tree[no], tree[2*no]);
      tree[2*no+1] = merge(tree[no], tree[2*no+1]);
      tree[no] = info{ 0, 0, C };
    };

    function<void(int,int,int,int,int,const info&)>
    add = [&](int no, int tl, int tr, int xl, int xr, const info& in) {
      if (xr < tl || tr < xl) {
      } else if (xl <= tl && tr <= xr) {
        tree[no] = merge(in, tree[no]);
      } else {
        push(no);
        int ts = (tl+tr)/2;
        add(2*no, tl, ts, xl, xr, in);
        add(2*no+1, ts+1, tr, xl, xr, in);
      }
    };

    REP(i,q) {
      add(1, 0, base-1, l[i], r[i], single(v[i]));
    }

    REP(i,base) {
      push(i);
    }

    REP(i,n) {
      a[i] = tree[base+i].y1;
    }

  } else if (sub_4) {

    vector<int> idx(n);
    REP(i,n) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int i, int j) { return c[i] < c[j]; });

    int ptr = 0;

    struct info {
      int a,b,c;
      info() : a(0), b(0), c(0) { }
    } in;

    REP(_i,q) {
      int i = q-1-_i;

      in.a -= v[i];

      while (ptr < n) {
        int j = idx[ptr];
        if (in.a >= c[j]) {
          a[j] = in.b;
        } else if (in.a <= in.c - c[j]) {
          a[j] = c[j] - (in.c - in.b);
        } else {
          break;
        }
        ++ptr;
      }
      
      if (in.a < 0) {
        in.c -= in.a;
        in.b -= in.a;
        in.a = 0;
      } else {
        in.c = max(in.c, in.a);
      }
    }

    while (ptr < n) {
      int j = idx[ptr];
      a[j] = in.b;
      ++ptr;
    }

  }

  return a;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 4 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 11440 KB Output is correct
2 Correct 175 ms 11356 KB Output is correct
3 Correct 188 ms 11360 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 229 ms 5076 KB Output is correct
3 Correct 72 ms 8760 KB Output is correct
4 Correct 520 ms 13512 KB Output is correct
5 Correct 504 ms 13516 KB Output is correct
6 Correct 507 ms 13508 KB Output is correct
7 Correct 514 ms 13508 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 66 ms 4960 KB Output is correct
4 Correct 89 ms 3468 KB Output is correct
5 Correct 175 ms 8112 KB Output is correct
6 Correct 148 ms 8132 KB Output is correct
7 Correct 153 ms 8248 KB Output is correct
8 Correct 138 ms 8160 KB Output is correct
9 Correct 160 ms 11444 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 316 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 203 ms 11440 KB Output is correct
7 Correct 175 ms 11356 KB Output is correct
8 Correct 188 ms 11360 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 229 ms 5076 KB Output is correct
11 Correct 72 ms 8760 KB Output is correct
12 Correct 520 ms 13512 KB Output is correct
13 Correct 504 ms 13516 KB Output is correct
14 Correct 507 ms 13508 KB Output is correct
15 Correct 514 ms 13508 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 66 ms 4960 KB Output is correct
19 Correct 89 ms 3468 KB Output is correct
20 Correct 175 ms 8112 KB Output is correct
21 Correct 148 ms 8132 KB Output is correct
22 Correct 153 ms 8248 KB Output is correct
23 Correct 138 ms 8160 KB Output is correct
24 Correct 160 ms 11444 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Incorrect 57 ms 2608 KB Output isn't correct
27 Halted 0 ms 0 KB -