Submission #240414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
240414	2020-06-19T15:11:33 Z	valerikk	Strange Device (APIO19_strange_device)	C++14	Compilation error	0 ms	0 KB

strange_device

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

#define ll __int128

istream &operator>>(istream &i, ll &x) {
    string s;
    i >> s;
    x = __int128(s);
}

ostream &operator<<(ostream &o, ll x) {
    o << string(x);
}

ll gcd(ll a, ll b) {
    while (b != 0LL) {
        a %= b;
        swap(a, b);
    }
    return a;
}

struct E {
    ll x;
    int k;
    ll l, r;

    bool operator<(const E& o) {
        return x < o.x || (x == o.x && k < o.k);
    }

    E() {}
    E(ll x, int k, ll l, ll r) : x(x), k(k), l(l), r(r) {}
};

ll n, a, b;

ll p;

vector<E> v;

void push(ll l, ll r, ll x, ll y) {
    v.emplace_back(l, 0, x, y);
    v.emplace_back(r+1, 1, x, y);
}

void add(ll l, ll r, ll x, ll y) {
    if (x <= y) {
        push(l, r, x, y);
    } else {
        push(l, r, 0LL, y);
        push(l, r, x, p-1LL);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a >> b;
    p = a/gcd(a, b+1);
    while (n--) {
        ll l, r;
        cin >> l >> r;
        ll x = l/b, y = r/b;
        if (x == y) {
            add(l%b, r%b, x%p, y%p);
        } else {
            if (y-x > 1) {
                add(0LL, b-1LL, (x+1LL)%p, (y-1LL)%p);
            }
            add(l%b, b-1LL, x%p, x%p);
            add(0LL, r%b, y%p, y%p);
        }
    }
    sort(v.begin(), v.end());
    multiset<pair<ll, ll>> s;
    ll ans = 0;
    for (int i = 0; i+1 < v.size(); ++i) {
        if (v[i].k) {
            s.erase(s.find({v[i].l, v[i].r}));
        } else {
            s.insert({v[i].l, v[i].r});
        }
        ll d = v[i+1].x-v[i].x;
        if (d) {
            vector<pair<ll, ll>> u;10
            for (auto ss : s) {
                u.emplace_back(ss.first, 1);
                u.emplace_back(ss.second+1, -1);
            }
            sort(u.begin(), u.end());
            ll q = 0;
            int bal = 0;
            for (int j = 0; j+1 < u.size(); ++j) {
                bal += u[j].second;
                if (bal) q += u[j+1].first-u[j].first;
            }
            ans += q*d;
        }
    }
    cout << ans;
    return 0;
}

Compilation message

strange_device.cpp: In function 'std::istream& operator>>(std::istream&, __int128&)':
strange_device.cpp:9:19: error: invalid cast from type 'std::__cxx11::string {aka std::__cxx11::basic_string<char>}' to type '__int128'
     x = __int128(s);
                   ^
strange_device.cpp:10:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
strange_device.cpp: In function 'std::ostream& operator<<(std::ostream&, __int128)':
strange_device.cpp:13:18: error: no matching function for call to 'std::__cxx11::basic_string<char>::basic_string(__int128&)'
     o << string(x);
                  ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from strange_device.cpp:1:
/usr/include/c++/7/bits/basic_string.h:604:9: note: candidate: template<class _InputIterator, class> std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(_InputIterator, _InputIterator, const _Alloc&)
         basic_string(_InputIterator __beg, _InputIterator __end,
         ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:604:9: note:   template argument deduction/substitution failed:
strange_device.cpp:13:18: note:   candidate expects 3 arguments, 1 provided
     o << string(x);
                  ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from strange_device.cpp:1:
/usr/include/c++/7/bits/basic_string.h:566:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string(basic_string&& __str, const _Alloc& __a)
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:566:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:562:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string(const basic_string& __str, const _Alloc& __a)
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:562:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:558:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(std::initializer_list<_Tp>, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc())
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:558:7: note:   no known conversion for argument 1 from '__int128' to 'std::initializer_list<char>'
/usr/include/c++/7/bits/basic_string.h:531:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string(basic_string&& __str) noexcept
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:531:7: note:   no known conversion for argument 1 from '__int128' to 'std::__cxx11::basic_string<char>&&'
/usr/include/c++/7/bits/basic_string.h:519:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type, _CharT, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]
       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc())
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:519:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:509:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>] <near match>
       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:509:7: note:   conversion of argument 1 would be ill-formed:
strange_device.cpp:13:18: error: invalid conversion from '__int128' to 'const char*' [-fpermissive]
     o << string(x);
                  ^
In file included from /usr/include/c++/7/string:52:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from strange_device.cpp:1:
/usr/include/c++/7/bits/basic_string.h:499:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _CharT*, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]
       basic_string(const _CharT* __s, size_type __n,
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:499:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:481:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]
       basic_string(const basic_string& __str, size_type __pos,
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:481:7: note:   candidate expects 4 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:465:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]
       basic_string(const basic_string& __str, size_type __pos,
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:465:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:450:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&, std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type, const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>; std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::size_type = long unsigned int]
       basic_string(const basic_string& __str, size_type __pos,
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:450:7: note:   candidate expects 3 arguments, 1 provided
/usr/include/c++/7/bits/basic_string.h:437:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string(const basic_string& __str)
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:437:7: note:   no known conversion for argument 1 from '__int128' to 'const std::__cxx11::basic_string<char>&'
/usr/include/c++/7/bits/basic_string.h:429:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string(const _Alloc&) [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string(const _Alloc& __a) _GLIBCXX_NOEXCEPT
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:429:7: note:   no known conversion for argument 1 from '__int128' to 'const std::allocator<char>&'
/usr/include/c++/7/bits/basic_string.h:420:7: note: candidate: std::__cxx11::basic_string<_CharT, _Traits, _Alloc>::basic_string() [with _CharT = char; _Traits = std::char_traits<char>; _Alloc = std::allocator<char>]
       basic_string()
       ^~~~~~~~~~~~
/usr/include/c++/7/bits/basic_string.h:420:7: note:   candidate expects 0 arguments, 1 provided
strange_device.cpp:14:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
strange_device.cpp: In function 'int main()':
strange_device.cpp:79:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i+1 < v.size(); ++i) {
                     ~~~~^~~~~~~~~~
strange_device.cpp:88:13: error: expected ';' before 'for'
             for (auto ss : s) {
             ^~~
strange_device.cpp:91:13: warning: statement has no effect [-Wunused-value]
             }
             ^
strange_device.cpp:95:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j+1 < u.size(); ++j) {
                             ~~~~^~~~~~~~~~