Submission #883484

#TimeUsernameProblemLanguageResultExecution timeMemory
883484vjudge1Ants and Sugar (JOI22_sugar)C++17
Compilation error
0 ms0 KiB
// https://oj.uz/problem/view/JOI22_sugar #include <bits/stdc++.h> using namespace std; /* Hall's theorem Answer = A - max(|S| - |NG(S)|) */ const int64_t inf = 1e18; class segtree_t { public: segtree_t *left, *right; int l, r, m; int64_t x[2][2], lazyx, lazy_mid, mid; segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { x[i][j] = 0; } } if (l == r) return; left = new segtree_t(l, m); right = new segtree_t(m + 1, r); } void Update(int s, int t, int64_t val) { if (l > t || r < s) return; if (s <= l && r <= t) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { x[i][j] += val; } } lazyx += val; lazy_mid += val; mid += val; return; } Down(); if (s <= m && m < t) mid += val; left->Update(s, t, val); right->Update(s, t, val); Up(); } void Down() { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { left->x[i][j] += lazyx; right->x[i][j] += lazyx; } } left->lazy_mid += lazy_mid; left->lazyx += lazyx; left->mid += lazy_mid; right->lazy_mid += lazy_mid; right->lazyx += lazyx; right->mid += lazy_mid; lazy_mid = lazyx = 0; } void Up() { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { x[i][j] = -inf; for (int k = 0; k < 2; k++) { x[i][j] = max(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid); } } } for (int i = 0; i < 2; i++) { x[i][0] = max(x[i][0], left->x[i][0]); x[0][i] = max(x[0][i], right->x[0][i]); } } }; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int q, L; cin >> q >> L; vector<int> t(q), a(q), x(q); for (int i = 0; i < q; i++) cin >> t[i] >> x[i] >> a[i]; vector<int> cord; for (int i = 0; i < q; i++) { if (t[i] == 1) cord.emplace_back(x[i]); } sort(cord.begin(), cord.end()); cord.resize(unique(cord.begin(), cord.end()) - cord.begin()); int N = cord.size(); segtree_t* tree = new segtree_t(0, N); int64_t A = 0; for (int i = 0; i < q; i++) { if (t[i] == 1) { A += a[i]; int y = lower_bound(cord.begin(), cord.end(), x[i]) - cord.begin(); tree->Update(y, y, +a[i]); } else { int u = lower_bound(cord.begin(), cord.end(), x[i] - L) - cord.begin(); int v = upper_bound(cord.begin(), cord.end(), x[i] + L) - cord.begin() - 1; tree->Update(u, v, -a[i]); } cout << A - max<int64_t>(0, tree->x[0][0]) << '\n'; } }

Compilation message (stderr)

sugar.cpp: In constructor 'segtree_t::segtree_t(int, int)':
sugar.cpp:21:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         segtree_t(int l, int r) : l(l), r(r), m(l + r >> 1) {
      |                                                 ~~^~~
sugar.cpp: In member function 'void segtree_t::Up()':
sugar.cpp:73:110: error: no matching function for call to 'max(int64_t&, long long int)'
   73 |                                         x[i][j] = max(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
      |                                                                                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sugar.cpp:3:
/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:
sugar.cpp:73:110: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   73 |                                         x[i][j] = max(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
      |                                                                                                              ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from sugar.cpp:3:
/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:
sugar.cpp:73:110: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'long long int')
   73 |                                         x[i][j] = max(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
      |                                                                                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sugar.cpp:3:
/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:
sugar.cpp:73:110: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   73 |                                         x[i][j] = max(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
      |                                                                                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from sugar.cpp:3:
/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:
sugar.cpp:73:110: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   73 |                                         x[i][j] = max(x[i][j], left->x[i][k] + right->x[k][j] - 1ll * k * mid);
      |                                                                                                              ^