oj.uz

Submission #437911

# Submission time Handle Problem Language Result Execution time Memory
437911 2021-06-27T09:26:33 Z monsoon Distributing Candies (IOI21_candies) C++17
67 / 100
 568 ms 18068 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;
  int sub_5 = ! (sub_1+sub_2+sub_3+sub_4);

  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 || sub_5) {

    const int max_C = 1000000000;
    const int C = sub_5 ? max_C : c[0];
    int base = 1;
    while (base < n) base *= 2;

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

      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);
      int sgn = G.last ?: F.last;
      return info{ x1, y1, y2, sgn };
    };

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

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

    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, 0 };
    };

    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) {
      info& in = tree[base+i];
      if (sub_3) {
        a[i] = in.y1;
      } else {
        if (in.y1 + max_C - in.y2 >= c[i]) {
          a[i] = in.y1;
        } else if (in.last > 0) {
          a[i] = min(in.y1, c[i]);
        } else {
          a[i] = max(c[i] - (max_C - in.y2), 0);
        }
      }
    }

  } 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 332 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 160 ms 11336 KB Output is correct
2 Correct 157 ms 11332 KB Output is correct
3 Correct 155 ms 11356 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 232 ms 5080 KB Output is correct
3 Correct 74 ms 10812 KB Output is correct
4 Correct 568 ms 15536 KB Output is correct
5 Correct 542 ms 17684 KB Output is correct
6 Correct 534 ms 18068 KB Output is correct
7 Correct 560 ms 17476 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 69 ms 4956 KB Output is correct
4 Correct 79 ms 3472 KB Output is correct
5 Correct 141 ms 8028 KB Output is correct
6 Correct 163 ms 12320 KB Output is correct
7 Correct 169 ms 12868 KB Output is correct
8 Correct 137 ms 11472 KB Output is correct
9 Correct 170 ms 16456 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 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 160 ms 11336 KB Output is correct
7 Correct 157 ms 11332 KB Output is correct
8 Correct 155 ms 11356 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 232 ms 5080 KB Output is correct
11 Correct 74 ms 10812 KB Output is correct
12 Correct 568 ms 15536 KB Output is correct
13 Correct 542 ms 17684 KB Output is correct
14 Correct 534 ms 18068 KB Output is correct
15 Correct 560 ms 17476 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 69 ms 4956 KB Output is correct
19 Correct 79 ms 3472 KB Output is correct
20 Correct 141 ms 8028 KB Output is correct
21 Correct 163 ms 12320 KB Output is correct
22 Correct 169 ms 12868 KB Output is correct
23 Correct 137 ms 11472 KB Output is correct
24 Correct 170 ms 16456 KB Output is correct
25 Correct 1 ms 296 KB Output is correct
26 Incorrect 102 ms 12064 KB Output isn't correct
27 Halted 0 ms 0 KB -