oj.uz

Submission #440928

# Submission time Handle Problem Language Result Execution time Memory
440928 2021-07-03T13:32:51 Z Quang Distributing Candies (IOI21_candies) C++17
100 / 100
 1927 ms 8540 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 {
      if (l[i] != l_block * block_size) {
        UpdateElement(l_block, l[i], (l_block + 1) * block_size - 1, v[i]);
        l_block++;
      }
      if (r[i] != (r_block + 1) * block_size - 1) {
        UpdateElement(r_block, r_block * block_size, r[i], v[i]);
        r_block--;
      }
      for (int j = l_block; j <= r_block; j++) {
        UpdateBlock(j, 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:199:5: note: in expansion of macro 'debug'
  199 |     debug(st);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:200:5: note: in expansion of macro 'debug'
  200 |     debug(cur_delta);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:201:5: note: in expansion of macro 'debug'
  201 |     debug(min_delta);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:202:5: note: in expansion of macro 'debug'
  202 |     debug(max_delta);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:203:5: note: in expansion of macro 'debug'
  203 |     debug(a);
      |     ^~~~~
candies.cpp:79:20: warning: statement has no effect [-Wunused-value]
   79 | #define debug(...) 42
      |                    ^~
candies.cpp:204:5: note: in expansion of macro 'debug'
  204 |     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 1 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 1909 ms 8300 KB Output is correct
2 Correct 1892 ms 8300 KB Output is correct
3 Correct 1906 ms 8304 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 250 ms 4952 KB Output is correct
3 Correct 82 ms 4812 KB Output is correct
4 Correct 1925 ms 8376 KB Output is correct
5 Correct 1906 ms 8500 KB Output is correct
6 Correct 1865 ms 8328 KB Output is correct
7 Correct 1829 ms 8412 KB Output is correct

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 211 ms 5060 KB Output is correct
4 Correct 83 ms 3880 KB Output is correct
5 Correct 1522 ms 8540 KB Output is correct
6 Correct 1531 ms 8516 KB Output is correct
7 Correct 1497 ms 8380 KB Output is correct
8 Correct 1536 ms 8516 KB Output is correct
9 Correct 1642 ms 8388 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 1 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 1909 ms 8300 KB Output is correct
7 Correct 1892 ms 8300 KB Output is correct
8 Correct 1906 ms 8304 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 250 ms 4952 KB Output is correct
11 Correct 82 ms 4812 KB Output is correct
12 Correct 1925 ms 8376 KB Output is correct
13 Correct 1906 ms 8500 KB Output is correct
14 Correct 1865 ms 8328 KB Output is correct
15 Correct 1829 ms 8412 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 211 ms 5060 KB Output is correct
19 Correct 83 ms 3880 KB Output is correct
20 Correct 1522 ms 8540 KB Output is correct
21 Correct 1531 ms 8516 KB Output is correct
22 Correct 1497 ms 8380 KB Output is correct
23 Correct 1536 ms 8516 KB Output is correct
24 Correct 1642 ms 8388 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 86 ms 3636 KB Output is correct
27 Correct 251 ms 4956 KB Output is correct
28 Correct 1920 ms 8380 KB Output is correct
29 Correct 1926 ms 8424 KB Output is correct
30 Correct 1915 ms 8384 KB Output is correct
31 Correct 1917 ms 8376 KB Output is correct
32 Correct 1927 ms 8380 KB Output is correct