oj.uz

Submission #435829

# Submission time Handle Problem Language Result Execution time Memory
435829 2021-06-23T19:05:25 Z monsoon Distributing Candies (IOI21_candies) C++17
40 / 100
 190 ms 11444 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_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.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 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 11444 KB Output is correct
2 Correct 157 ms 11368 KB Output is correct
3 Correct 161 ms 11352 KB Output is correct

Subtask #3
0 / 27.0

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

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 67 ms 4932 KB Output is correct
4 Correct 79 ms 3404 KB Output is correct
5 Correct 135 ms 8116 KB Output is correct
6 Correct 167 ms 8132 KB Output is correct
7 Correct 150 ms 8120 KB Output is correct
8 Correct 138 ms 8104 KB Output is correct
9 Correct 150 ms 11444 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 2 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 5 ms 332 KB Output is correct
6 Correct 190 ms 11444 KB Output is correct
7 Correct 157 ms 11368 KB Output is correct
8 Correct 161 ms 11352 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Incorrect 65 ms 4964 KB Output isn't correct
11 Halted 0 ms 0 KB -