제출 #1355454

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355454		otarius	Bubble Sort 2 (JOI18_bubblesort2)	C++20	컴파일 에러	0 ms	0 KiB

bubblesort2

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rngl(chrono::steady_clock::now().time_since_epoch().count());

// #define int long long
// #define int unsigned long long

// #define ordered_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
// #define ordered_multiset(T) tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>

// const ll mod = 1e9 + 7;
// const ll mod = 998244353;

const ll inf = 1e9;
const ll biginf = 1e18;
const int maxN = 5 * 1e5 + 15;

int t[4 * maxN], lazy[4 * maxN];
void prop(int v, int tl, int tr) {
    t[v] += lazy[v];
    if (tl != tr) {
        lazy[2 * v] += lazy[v];
        lazy[2 * v + 1] += lazy[v];
    } lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, int add) {
    if (lazy[v]) prop(v, tl, tr);
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
        lazy[v] += add; prop(v, tl, tr); return;
    } int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, min(r, tm), add);
    update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
    vector<pii> arr;
    for (int i = 1; i <= n; i++) arr.pb({a[i], i});
    for (int i = 1; i <= q; i++) arr.pb({x[i], v[i]});

    sort(all(arr)); int m = arr.size();
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(all(arr), {a[i], i}) - arr.begin() + 1;
        update(1, 1, m, pos, pos, i + 1);
        update(1, 1, m, pos + 1, m, -1);
    }

    vector<int> ans(q);
    for (int i = 1; i <= q; i++) {
        int pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
        update(1, 1, m, pos, pos, -(x[i] + 1));
        update(1, 1, m, pos + 1, m, 1);
        a[x[i]] = v[i];
        pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
        update(1, 1, m, pos, pos, x[i] + 1);
        update(1, 1, m, pos + 1, m, -1);
        ans[i] = t[1] - 1;
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:56:26: error: 'n' was not declared in this scope
   56 |     for (int i = 1; i <= n; i++) arr.pb({a[i], i});
      |                          ^
bubblesort2.cpp:57:26: error: 'q' was not declared in this scope
   57 |     for (int i = 1; i <= q; i++) arr.pb({x[i], v[i]});
      |                          ^
bubblesort2.cpp:60:25: error: 'n' was not declared in this scope
   60 |     for (int i = 0; i < n; i++) {
      |                         ^
bubblesort2.cpp:61:30: error: no matching function for call to 'lower_bound(std::vector<std::pair<int, int> >::iterator, std::vector<std::pair<int, int> >::iterator, <brace-enclosed initializer list>)'
   61 |         int pos = lower_bound(all(arr), {a[i], i}) - arr.begin() + 1;
      |                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from bubblesort2.cpp:1:
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note: candidate: 'template<class _ForwardIterator, class _Tp> constexpr _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
 1498 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:61:30: note:   couldn't deduce template parameter '_Tp'
   61 |         int pos = lower_bound(all(arr), {a[i], i}) - arr.begin() + 1;
      |                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:2005:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> constexpr _FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)'
 2005 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:2005:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:61:30: note:   candidate expects 4 arguments, 3 provided
   61 |         int pos = lower_bound(all(arr), {a[i], i}) - arr.begin() + 1;
      |                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:66:21: error: 'q' was not declared in this scope
   66 |     vector<int> ans(q);
      |                     ^
bubblesort2.cpp:68:30: error: no matching function for call to 'lower_bound(std::vector<std::pair<int, int> >::iterator, std::vector<std::pair<int, int> >::iterator, <brace-enclosed initializer list>)'
   68 |         int pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
      |                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note: candidate: 'template<class _ForwardIterator, class _Tp> constexpr _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
 1498 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:68:30: note:   couldn't deduce template parameter '_Tp'
   68 |         int pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
      |                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:2005:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> constexpr _FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)'
 2005 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:2005:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:68:30: note:   candidate expects 4 arguments, 3 provided
   68 |         int pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
      |                   ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:72:26: error: no matching function for call to 'lower_bound(std::vector<std::pair<int, int> >::iterator, std::vector<std::pair<int, int> >::iterator, <brace-enclosed initializer list>)'
   72 |         pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note: candidate: 'template<class _ForwardIterator, class _Tp> constexpr _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
 1498 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:1498:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:72:26: note:   couldn't deduce template parameter '_Tp'
   72 |         pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:2005:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> constexpr _FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)'
 2005 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:2005:5: note:   template argument deduction/substitution failed:
bubblesort2.cpp:72:26: note:   candidate expects 4 arguments, 3 provided
   72 |         pos = lower_bound(all(arr), {a[x[i]], x[i]}) - arr.begin() + 1;
      |               ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~