제출 #437911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
437911		monsoon	Distributing Candies (IOI21_candies)	C++17	67 / 100	568 ms	18068 KiB

candies

#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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33