oj.uz

Submission #651178

# Submission time Handle Problem Language Result Execution time Memory
651178 2022-10-17T15:25:32 Z bicsi Fire (JOI20_ho_t5) C++14
19 / 100
 429 ms 36112 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int n, q; cin >> n >> q;
  vector<int> v(n);
  for (int i = 0; i < n; ++i) cin >> v[i];
  
  vector<int> len[2];
  for (int rev = 0; rev < 2; ++rev) {
    vector<int> stk = {-1};
    for (int i = 0; i < n; ++i) {
      while (stk.size() > 1 && v[i] + rev > v[stk.back()])
        stk.pop_back();
      len[rev].push_back(i - stk.back());
      stk.push_back(i);
    }
    reverse(v.begin(), v.end());
  }
  reverse(len[1].begin(), len[1].end());
  
  int t = 0;
  auto get_range = [&](int i) {
    int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
    int r = i + min(t + 1, len[1][i]);
    return make_pair(l, r);
  };
  auto cmp = [&](int i, int j) {
    assert(i >= 0);
    if (j < 0) {
      auto [l, r] = get_range(i);
      return r < (~j);
    }
    return i < j;
  };
  set<int, decltype(cmp)> S(cmp);
  for (int i = 0; i < n; ++i)
    S.insert(i);
  
  vector<pair<int, long long>> fw(n + 1);
  auto update = [&](int i, int k, long long c) {
    for (++i; i <= n; i += (i & -i)) {
      fw[i].first += k;
      fw[i].second += c;
    }
  };
  auto query = [&](int pos) {
    int i = *S.lower_bound(~pos);
    auto [l, r] = get_range(i);
    assert(l <= pos && r >= pos);
    long long ans = 1LL * (min(r, pos) - l) * v[i];
    for (; i > 0; i -= (i & -i))
      ans += 1LL * fw[i].first * t + fw[i].second;
    return ans;
  };
  for (int i = 0; i < n; ++i) 
    update(i, v[i], v[i]);

  vector<tuple<int, int, int>> evs;
  for (int i = 0; i < n; ++i) {
    evs.emplace_back(len[1][i] - 1, 0, i);
    if (len[0][i] <= i) {
      evs.emplace_back(len[0][i] - 1, 0, i);
      evs.emplace_back(len[0][i] + len[1][i] - 1, 1, i);
    }
  }
  vector<pair<int, int>> qs(q);
  for (int i = 0; i < q; ++i) {
    int t, l, r; cin >> t >> l >> r;
    qs[i] = {l - 1, r};
    evs.emplace_back(t, 2, i);
  }
  sort(evs.begin(), evs.end());
  vector<long long> ans(q);
  for (auto& [t_, typ, i] : evs) {
    t = t_;
    if (typ == 0) { // decrease slope
      update(i, -v[i], 1LL * t * v[i]);
    } else if (typ == 1) { // erase
      S.erase(i);
      update(i, v[i], -1LL * t * v[i]);
    } else { // query
      auto [l, r] = qs[i];
      ans[i] = query(r) - query(l);  
    }
  }
  for (int i = 0; i < q; ++i) 
    cout << ans[i] << '\n';

  return 0;
}

Compilation message

ho_t5.cpp: In lambda function:
ho_t5.cpp:35:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |       auto [l, r] = get_range(i);
      |            ^
ho_t5.cpp: In lambda function:
ho_t5.cpp:53:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     auto [l, r] = get_range(i);
      |          ^
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   79 |   for (auto& [t_, typ, i] : evs) {
      |              ^
ho_t5.cpp:87:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |       auto [l, r] = qs[i];
      |            ^

Subtask #1
0 / 1.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 317 ms 30236 KB Output is correct
3 Correct 297 ms 35388 KB Output is correct
4 Correct 332 ms 35592 KB Output is correct
5 Correct 342 ms 35872 KB Output is correct
6 Correct 332 ms 35344 KB Output is correct
7 Correct 335 ms 35864 KB Output is correct
8 Correct 339 ms 35996 KB Output is correct
9 Correct 339 ms 35920 KB Output is correct
10 Correct 310 ms 35244 KB Output is correct
11 Correct 320 ms 36112 KB Output is correct
12 Correct 309 ms 35132 KB Output is correct
13 Correct 345 ms 35624 KB Output is correct
14 Correct 339 ms 35544 KB Output is correct
15 Correct 337 ms 35632 KB Output is correct
16 Correct 321 ms 35368 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 308 ms 29236 KB Output is correct
3 Correct 301 ms 28760 KB Output is correct
4 Correct 329 ms 29880 KB Output is correct
5 Correct 311 ms 28932 KB Output is correct
6 Correct 320 ms 29372 KB Output is correct
7 Correct 303 ms 29400 KB Output is correct
8 Correct 318 ms 29184 KB Output is correct
9 Correct 321 ms 28840 KB Output is correct
10 Correct 301 ms 28600 KB Output is correct
11 Correct 322 ms 29752 KB Output is correct
12 Correct 305 ms 29352 KB Output is correct
13 Correct 306 ms 29608 KB Output is correct
14 Correct 312 ms 29076 KB Output is correct
15 Correct 299 ms 29616 KB Output is correct
16 Correct 299 ms 29292 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 28168 KB Output is correct
2 Correct 401 ms 28216 KB Output is correct
3 Correct 421 ms 28916 KB Output is correct
4 Correct 383 ms 28136 KB Output is correct
5 Correct 415 ms 28296 KB Output is correct
6 Correct 381 ms 28240 KB Output is correct
7 Correct 405 ms 28820 KB Output is correct
8 Correct 423 ms 28656 KB Output is correct
9 Correct 421 ms 28260 KB Output is correct
10 Correct 426 ms 28576 KB Output is correct
11 Correct 428 ms 28348 KB Output is correct
12 Correct 429 ms 28564 KB Output is correct
13 Correct 407 ms 28304 KB Output is correct
14 Correct 416 ms 28412 KB Output is correct

Subtask #5
0 / 80.0

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