oj.uz

Submission #440924

# Submission time Handle Problem Language Result Execution time Memory
440924 2021-07-03T13:29:44 Z Quang Distributing Candies (IOI21_candies) C++17
100 / 100
 2460 ms 14916 KB 
#include "candies.h"

#include <bits/stdc++.h>

using namespace std;

const int INF = 1.01e9;

// source: tourist
template <typename A, typename B>
string to_string(pair<A, B> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template <typename T>
inline bool max_to(T &u, const T &v) {
  return u < v ? (u = v, true) : false;
}

template <typename T>
inline bool min_to(T &u, const T &v) {
  return u > v ? (u = v, true) : false;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  int n = c.size();
  int q = l.size();
  int block_size = sqrt(n);
  int num_block = (n + block_size - 1) / block_size;
  vector<vector<int>> id_in_block(num_block, vector<int>());
  vector<vector<pair<int, int>>> st(num_block, vector<pair<int, int>>());
  
  for (int i = 0; i < n; i++) {
    id_in_block[i / block_size].push_back(i);
  }
  for (int i = 0; i < num_block; i++) {
    sort(id_in_block[i].begin(), id_in_block[i].end(), [&](int u, int v) {
      return c[u] < c[v];
    });
    st[i].push_back({INF, 0});
  }

  debug(block_size, num_block);

  vector<int> a(n, 0);
  vector<long long> cur_delta(num_block, 0);
  vector<long long> min_delta(num_block, 0);
  vector<long long> max_delta(num_block, 0);

  auto UpdateStack = [&](int id, int value, int type) {
    int sum = 0;
    int last = 0;
    while (!st[id].empty()) {
      debug(st[id].size());
      if (st[id].back().second == type) {
        last = st[id].back().first;
        st[id].pop_back();
        continue;
      }
      if (sum + st[id].back().first - last > value) {
        st[id].push_back({last + value - sum, type});
        break;
      }
      sum += st[id].back().first - last;
      last = st[id].back().first;
      st[id].pop_back();
    }
    if (st[id].empty()) {
      st[id].push_back({INF, type});
    }
  };

  auto UpdateBlock = [&](int id, int value) {
    debug("update block", id, value);
    if (value > 0) UpdateStack(id, value, 1);
    else UpdateStack(id, -value, 0);
    cur_delta[id] += value;
    min_to(min_delta[id], cur_delta[id]);
    max_to(max_delta[id], cur_delta[id]);
  };

  auto Commit = [&](int id) {
    int value = 0;
    int cur = 0;
    int last = 0;
    for (int i = (int)st[id].size() - 1; i >= 0; i--) {
      while (cur < (int)id_in_block[id].size() && c[id_in_block[id][cur]] < st[id][i].first) {
        int u = id_in_block[id][cur];
        int now = value + (c[u] - last) * st[id][i].second;
        a[u] = max(0ll, min_delta[id] + min(1ll * a[u], c[u] - max_delta[id])) + now;
        cur++;
      }
      value += (st[id][i].first - last) * st[id][i].second;
      last = st[id][i].first;
    }
    cur_delta[id] = min_delta[id] = max_delta[id] = 0;
    st[id].clear();
    st[id].push_back({INF, 0});
  };

  auto UpdateElement = [&](int id, int l, int r, int value) {
    debug("update", id, l, r, value);
    Commit(id);
    for (int i = l; i <= r; i++) {
      a[i] += value;
      min_to(a[i], c[i]);
      max_to(a[i], 0);   
    }
  };

  for (int i = 0; i < q; i++) {
    debug(i);
    debug(l[i], r[i], v[i]);
    int l_block = l[i] / block_size;
    int r_block = r[i] / block_size;
    if (l_block == r_block) {
      UpdateElement(l_block, l[i], r[i], v[i]);
    } else {
      for (int j = l_block + 1; j < r_block; j++) {
        UpdateBlock(j, v[i]);
      }
      UpdateElement(l_block, l[i], (l_block + 1) * block_size - 1, v[i]);
      UpdateElement(r_block, r_block * block_size, r[i], v[i]);
    }
    debug(st);
    debug(cur_delta);
    debug(min_delta);
    debug(max_delta);
    debug(a);
    debug(c);
  }

  for (int i = 0; i < num_block; i++) {
    Commit(i);
  }

  return a; 
}

Compilation message

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:111:3: note: in expansion of macro 'debug'
  111 |   debug(block_size, num_block);
      |   ^~~~~
candies.cpp: In lambda function:
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:122:7: note: in expansion of macro 'debug'
  122 |       debug(st[id].size());
      |       ^~~~~
candies.cpp: In lambda function:
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:142:5: note: in expansion of macro 'debug'
  142 |     debug("update block", id, value);
      |     ^~~~~
candies.cpp: In lambda function:
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:170:5: note: in expansion of macro 'debug'
  170 |     debug("update", id, l, r, value);
      |     ^~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:180:5: note: in expansion of macro 'debug'
  180 |     debug(i);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:181:5: note: in expansion of macro 'debug'
  181 |     debug(l[i], r[i], v[i]);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:193:5: note: in expansion of macro 'debug'
  193 |     debug(st);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:194:5: note: in expansion of macro 'debug'
  194 |     debug(cur_delta);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:195:5: note: in expansion of macro 'debug'
  195 |     debug(min_delta);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:196:5: note: in expansion of macro 'debug'
  196 |     debug(max_delta);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:197:5: note: in expansion of macro 'debug'
  197 |     debug(a);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:198:5: note: in expansion of macro 'debug'
  198 |     debug(c);
      |     ^~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1919 ms 8300 KB Output is correct
2 Correct 1916 ms 8300 KB Output is correct
3 Correct 1915 ms 8296 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 254 ms 5036 KB Output is correct
3 Correct 87 ms 4780 KB Output is correct
4 Correct 1948 ms 8376 KB Output is correct
5 Correct 1894 ms 14788 KB Output is correct
6 Correct 1864 ms 14916 KB Output is correct
7 Correct 1833 ms 14404 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 284 ms 4960 KB Output is correct
4 Correct 95 ms 3764 KB Output is correct
5 Correct 2334 ms 8424 KB Output is correct
6 Correct 2349 ms 8436 KB Output is correct
7 Correct 2333 ms 8368 KB Output is correct
8 Correct 2359 ms 8436 KB Output is correct
9 Correct 2460 ms 8296 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 1919 ms 8300 KB Output is correct
7 Correct 1916 ms 8300 KB Output is correct
8 Correct 1915 ms 8296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 254 ms 5036 KB Output is correct
11 Correct 87 ms 4780 KB Output is correct
12 Correct 1948 ms 8376 KB Output is correct
13 Correct 1894 ms 14788 KB Output is correct
14 Correct 1864 ms 14916 KB Output is correct
15 Correct 1833 ms 14404 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 284 ms 4960 KB Output is correct
19 Correct 95 ms 3764 KB Output is correct
20 Correct 2334 ms 8424 KB Output is correct
21 Correct 2349 ms 8436 KB Output is correct
22 Correct 2333 ms 8368 KB Output is correct
23 Correct 2359 ms 8436 KB Output is correct
24 Correct 2460 ms 8296 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 93 ms 5020 KB Output is correct
27 Correct 253 ms 7636 KB Output is correct
28 Correct 1955 ms 12932 KB Output is correct
29 Correct 1910 ms 13352 KB Output is correct
30 Correct 1917 ms 13640 KB Output is correct
31 Correct 1929 ms 13704 KB Output is correct
32 Correct 1932 ms 13908 KB Output is correct