oj.uz

Submission #435786

# Submission time Handle Problem Language Result Execution time Memory
435786 2021-06-23T17:57:06 Z monsoon Distributing Candies (IOI21_candies) C++17
3 / 100
 167 ms 9312 KB 
#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.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 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 9312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 80 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
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 Incorrect 75 ms 4956 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 1 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Incorrect 167 ms 9312 KB Output isn't correct
7 Halted 0 ms 0 KB -