Submission #651179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
651179	2022-10-17T15:26:43 Z	bicsi	Fire (JOI20_ho_t5)	C++14	Compilation error	0 ms	0 KB

ho_t5

#include <bits/stdc++.h>
#define int long long 

using namespace std;

int32_t 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:29:61: error: no matching function for call to 'max(int, long long int)'
   29 |     int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
      |                                                             ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t5.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:29:61: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   29 |     int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
      |                                                             ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ho_t5.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:29:61: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   29 |     int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
      |                                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from ho_t5.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:29:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   29 |     int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
      |                                                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from ho_t5.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
ho_t5.cpp:29:61: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   29 |     int l = len[0][i] > i ? i : i + max(0, t - len[0][i] + 1);
      |                                                             ^
ho_t5.cpp: In lambda function:
ho_t5.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |       auto [l, r] = get_range(i);
      |            ^
ho_t5.cpp: In lambda function:
ho_t5.cpp:54:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     auto [l, r] = get_range(i);
      |          ^
ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:80:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |   for (auto& [t_, typ, i] : evs) {
      |              ^
ho_t5.cpp:88:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |       auto [l, r] = qs[i];
      |            ^