제출 #435829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435829		monsoon	사탕 분배 (IOI21_candies)	C++17	40 / 100	190 ms	11444 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_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_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: 0 / 27
• Subtask 4: 29 / 29
• Subtask 5: 0 / 33