oj.uz

Submission #651177

# Submission time Handle Problem Language Result Execution time Memory
651177 2022-10-17T15:16:34 Z bicsi Fire (JOI20_ho_t5) C++14
13 / 100
 435 ms 34472 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<int> 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 1 ms 212 KB Output is correct
2 Incorrect 1 ms 320 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 324 ms 33792 KB Output is correct
3 Correct 320 ms 33188 KB Output is correct
4 Correct 336 ms 34472 KB Output is correct
5 Correct 320 ms 33576 KB Output is correct
6 Correct 314 ms 33800 KB Output is correct
7 Correct 325 ms 33940 KB Output is correct
8 Correct 312 ms 33820 KB Output is correct
9 Correct 329 ms 33372 KB Output is correct
10 Correct 323 ms 33080 KB Output is correct
11 Correct 347 ms 34336 KB Output is correct
12 Correct 326 ms 33832 KB Output is correct
13 Correct 318 ms 34220 KB Output is correct
14 Correct 320 ms 33556 KB Output is correct
15 Correct 316 ms 34224 KB Output is correct
16 Correct 326 ms 33812 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 31184 KB Output is correct
2 Correct 409 ms 31256 KB Output is correct
3 Correct 422 ms 32028 KB Output is correct
4 Correct 399 ms 31380 KB Output is correct
5 Correct 414 ms 31392 KB Output is correct
6 Correct 431 ms 31356 KB Output is correct
7 Correct 418 ms 31932 KB Output is correct
8 Correct 433 ms 31732 KB Output is correct
9 Correct 432 ms 31400 KB Output is correct
10 Correct 417 ms 31644 KB Output is correct
11 Correct 435 ms 31600 KB Output is correct
12 Correct 433 ms 31580 KB Output is correct
13 Correct 429 ms 31532 KB Output is correct
14 Correct 401 ms 31512 KB Output is correct

Subtask #5
0 / 80.0

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