Submission #170212

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
170212	2019-12-24T08:49:44 Z	theboatman	Simple game (IZhO17_game)	C++17	Compilation error	0 ms	0 KB

game

#include <bits/stdc++.h>

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
template <typename T> using ordset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const long long ll(INF) = 1e18 + 10;
const int int(inf) = 1e9 + 10;
const int N = int(1e6) + 10;

struct Tree {
    int n, timer;
    vector <ordset <pair <int, int> > > t;

    void init(int _n) {
        n = _n;
        timer = 0;

        t.resize(n + 1);
    }

    void add(int pos, int val) {
        for(int i = pos; i <= n; i += i & -i) {
            t[i].insert({val, timer++});
        }
    }

    void del(int pos, int val) {
        for(int i = pos; i <= n; i += i & -i) {
            t[i].erase(t[i].lower_bound({val, -inf}));
        }
    }

    int get(int pos, int r) {
        int ans = 0;
        for(int i = pos; i > 0; i -= i & -i) {
            ans += t[i].size() - t[i].order_of_key({r + 1, -inf});
        }

        return ans;
    }
};

void brute() {
    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    while(m--) {
        int type;
        cin >> type;

        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;

            a[pos] = val;
        }
        else {
            int x;
            cin >> x;

            int ans = 0;
            for(auto i : a) {
                if (i == x) {
                    ans++;
                }
            }

            for(int i = 1; i < n; i++) {
                int l = min(a[i], a[i - 1]);
                int r = max(a[i], a[i - 1]);

                if (l < x && x < r) {
                    ans++;
                }
            }

            cout << ans << "\n";
        }
    }
}

int main() {
    //freopen("game.in", "r", stdin);
    //freopen("game.out", "w", stdout);

    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    Tree osu;
    osu.init(N);

    for(int i = 1; i < n; i++) {
        osu.add(min(a[i], a[i - 1]), max(a[i], a[i - 1]));
    }

    vector <int> cnt(N);
    for(int i = 0; i < n; i++) {
        cnt[a[i]]++;
    }

    for(int iq = 0; iq < m; iq++) {
        int type;
        cin >> type;

        if (type == 2) {
            int x;
            cin >> x;

            cout << cnt[x] + osu.get(x - 1, x) << "\n";
        }
        else {
            int pos, val;
            cin >> pos >> val;
            pos--;

            if (pos > 0) {
                osu.del(min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]));
            }

            if (pos < n - 1) {
                osu.del(min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]));
            }

            cnt[a[pos]]--;
            a[pos] = val;
            cnt[a[pos]]++;

            if (pos > 0) {
                osu.add(min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]));
            }

            if (pos < n - 1) {
                osu.add(min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]));
            }
        }
    }

    return 0;
}

/*
*/

Compilation message

game.cpp:20:23: error: 'const long long int ll' redeclared as different kind of symbol
 const long long ll(INF) = 1e18 + 10;
                       ^
game.cpp:17:19: note: previous declaration 'typedef long long int ll'
 typedef long long ll;
                   ^~
game.cpp:20:20: error: 'INF' was not declared in this scope
 const long long ll(INF) = 1e18 + 10;
                    ^~~
game.cpp:20:20: note: suggested alternative: 'SING'
 const long long ll(INF) = 1e18 + 10;
                    ^~~
                    SING
game.cpp:21:18: error: two or more data types in declaration of 'inf'
 const int int(inf) = 1e9 + 10;
                  ^
game.cpp: In member function 'void Tree::del(int, int)':
game.cpp:43:48: error: 'inf' was not declared in this scope
             t[i].erase(t[i].lower_bound({val, -inf}));
                                                ^~~
game.cpp:43:48: note: suggested alternative: 'ynf'
             t[i].erase(t[i].lower_bound({val, -inf}));
                                                ^~~
                                                ynf
game.cpp:43:52: error: no matching function for call to '__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update, std::allocator<char> >::lower_bound(<brace-enclosed initializer list>)'
             t[i].erase(t[i].lower_bound({val, -inf}));
                                                    ^
In file included from /usr/include/c++/7/ext/pb_ds/detail/container_base_dispatch.hpp:84:0,
                 from /usr/include/c++/7/ext/pb_ds/assoc_container.hpp:48,
                 from game.cpp:9:
/usr/include/c++/7/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp:62:1: note: candidate: __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::point_iterator __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::lower_bound(__gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::key_const_reference) [with Key = std::pair<int, int>; Mapped = __gnu_pbds::null_type; Cmp_Fn = std::less<std::pair<int, int> >; Node_And_It_Traits = __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >; _Alloc = std::allocator<char>; __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::point_iterator = __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >; __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::key_const_reference = const std::pair<int, int>&]
 PB_DS_CLASS_C_DEC::
 ^
/usr/include/c++/7/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp:62:1: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::key_const_reference {aka const std::pair<int, int>&}'
/usr/include/c++/7/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp:43:1: note: candidate: __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::point_const_iterator __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::lower_bound(__gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::key_const_reference) const [with Key = std::pair<int, int>; Mapped = __gnu_pbds::null_type; Cmp_Fn = std::less<std::pair<int, int> >; Node_And_It_Traits = __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >; _Alloc = std::allocator<char>; __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::point_const_iterator = __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >; __gnu_pbds::detail::bin_search_tree_set<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc>::key_const_reference = const std::pair<int, int>&]
 PB_DS_CLASS_C_DEC::
 ^
/usr/include/c++/7/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp:43:1: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::key_const_reference {aka const std::pair<int, int>&}'
game.cpp: In member function 'int Tree::get(int, int)':
game.cpp:50:61: error: 'inf' was not declared in this scope
             ans += t[i].size() - t[i].order_of_key({r + 1, -inf});
                                                             ^~~
game.cpp:50:61: note: suggested alternative: 'ynf'
             ans += t[i].size() - t[i].order_of_key({r + 1, -inf});
                                                             ^~~
                                                             ynf
game.cpp:50:65: error: no matching function for call to '__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update, std::allocator<char> >::order_of_key(<brace-enclosed initializer list>)'
             ans += t[i].size() - t[i].order_of_key({r + 1, -inf});
                                                                 ^
In file included from game.cpp:8:0:
/usr/include/c++/7/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp:76:1: note: candidate: __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::size_type __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::order_of_key(__gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::key_const_reference) const [with Node_CItr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >; Node_Itr = __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >; Cmp_Fn = std::less<std::pair<int, int> >; _Alloc = std::allocator<char>; __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::size_type = long unsigned int; __gnu_pbds::tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>::key_const_reference = const std::pair<int, int>&]
 PB_DS_CLASS_C_DEC::
 ^
/usr/include/c++/7/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp:76:1: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to '__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, std::less<std::pair<int, int> >, std::allocator<char> >::key_const_reference {aka const std::pair<int, int>&}'