Submission #435786

#	Time	Username	Problem	Language	Result	Execution time	Memory
435786		monsoon	Distributing Candies (IOI21_candies)	C++17	3 / 100	167 ms	9312 KiB

candies

#include <bits/stdc++.h>
#include "candies.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)

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;

  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<int> 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], c[i]);
    }

  }

  return a;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33