Submission #1146259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146259		vladilius	Strange Device (APIO19_strange_device)	C++20	Compilation error	0 ms	0 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define arr4 array<ll, 4>

struct ST{
    struct node{
        node *l, *r;
        int m; ll c, p;
        node(ll x){
            l = r = 0;
            m = p = 0; c = x;
        }
    };
    ll n;
    node *rt;
    ST(ll ns){
        n = ns;
        rt = new node(n);
    }
    void push(node *v){
        if (!(v -> p)) return;
        v -> l -> m += v -> p;
        v -> r -> m += v -> p;
        v -> l -> p += v -> p;
        v -> r -> p += v -> p;
        v -> p = 0;
    }
    void add(node *v, ll tl, ll tr, ll l, ll r, int x){
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r){
            v -> m += x;
            v -> p += x;
            return;
        }
        ll tm = (tl + tr) / 2;
        if (!(v -> l)) v -> l = new node(tm - tl + 1);
        if (!(v -> r)) v -> r = new node(tr - tm);
        push(v);
        add(v -> l, tl, tm, l, r, x);
        add(v -> r, tm + 1, tr, l, r, x);
        v -> m = min(v -> l -> m, v -> r -> m);
        v -> c = 0;
        if (v -> l -> m == v -> m) v -> c += v -> l -> c;
        if (v -> r -> m == v -> m) v -> c += v -> r -> c;
    };
    void add(ll l, ll r, int x){
        add(rt, 1, n, l, r, x);
    }
    ll get(){
        ll out = n;
        if (!(rt -> m)) out -= rt -> c;
        return out;
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; ll a, b; cin>>n>>a>>b;
    vector<ll> l(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>l[i]>>r[i];
    }
    
    vector<arr4> all;
    
    a /= gcd(a, b + 1);
    for (int i = 1; i <= n; i++){
        ll r1 = r[i] % b, r2 = l[i] % b - 1;
        if (r2 == -1) r2 += b;
        
        if (r1 > r2) swap(r1, r2);

        vector<pll> f;
        if ((r[i] - l[i] + 1) >= b) f.pb({0, b - 1});
        else {
            ll x = l[i] % b, y = r[i] % b;
            if (x <= y){
                f.pb({x, y});
            }
            else {
                f.pb({x, b - 1});
                f.pb({0, y});
            }
        }
        
        vector<arr4> pos;
        
        ll L = ceil((long double) * l[i] / b), R = r[i] / b;
        pos.pb({0, r1, L, R});
        
        L = ceil((long double) * (l[i] - r2) / b); R = (r[i] - r2) / b;
        if (r1 + 1 <= r2) pos.pb({r1 + 1, r2, L, R});
      
        L = ceil((long double) * (l[i] - (r2 + 1)) / b); R = (r[i] - (r2 + 1)) / b;
        if (r2 + 1 <= b - 1) pos.pb({r2 + 1, b - 1, L, R});
        
        for (auto [l1, r1, L, R]: pos){
            for (auto [l2, r2]: f){
                ll l3 = max(l1, l2), r3 = min(r1, r2);
                if (l3 <= r3){
                    all.pb({l3, i, L, R});
                    all.pb({r3 + 1, i, -1, -1});
                }
            }
        }
    }
    
    auto cmp = [&](arr4 x, arr4 y){
        if (x[0] != y[0]) return x[0] < y[0];
        return x[2] < y[2];
    };
    
    sort(all.begin(), all.end(), cmp);
    
    vector<ll> L(n + 1, -1), R(n + 1, -1);
    
    ll out = 0;
    int i1 = 0;
    ST T(a);
    
    auto add = [&](ll l, ll r, int x){
        if ((r - l + 1) >= a){
            T.add(1, a, x);
            return;
        }
        l %= a; r %= a;
        if (l <= r){
            T.add(l + 1, r + 1, x);
            return;
        }
        if (l < a) T.add(l + 1, a, x);
        T.add(1, r + 1, x);
    };

    while (i1 < all.size()){
        int j = i1;
        while (j < all.size() && all[i1][0] == all[j][0]){
            int i = (int) all[j][1];
            if (L[i] != -1){
                if (L[i] <= R[i]) add(L[i], R[i], -1);
            }
            
            L[i] = all[j][2]; R[i] = all[j][3];
            if (L[i] != -1 && L[i] <= R[i]) add(L[i], R[i], 1);
            
            j++;
        }
        
        ll R = 0;
        if (j == all.size()){
            R = b - 1;
        }
        else {
            R = all[j][0] - 1;
        }

        out += 1LL * (R - all[i1][0] + 1) * T.get();
        
        i1 = j;
    }
    
    cout<<out<<"\n";
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:97:35: error: invalid type argument of unary '*' (have '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
   97 |         ll L = ceil((long double) * l[i] / b), R = r[i] / b;
strange_device.cpp:98:27: error: 'R' was not declared in this scope
   98 |         pos.pb({0, r1, L, R});
      |                           ^
strange_device.cpp:98:15: error: no matching function for call to 'std::vector<std::array<long long int, 4> >::push_back(<brace-enclosed initializer list>)'
   98 |         pos.pb({0, r1, L, R});
      |         ~~~~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from strange_device.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<long long int, 4>; _Alloc = std::allocator<std::array<long long int, 4> >; std::vector<_Tp, _Alloc>::value_type = std::array<long long int, 4>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<long long int, 4>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<long long int, 4>; _Alloc = std::allocator<std::array<long long int, 4> >; std::vector<_Tp, _Alloc>::value_type = std::array<long long int, 4>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<long long int, 4> >::value_type&&' {aka 'std::array<long long int, 4>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
strange_device.cpp:100:32: error: invalid type argument of unary '*' (have '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  100 |         L = ceil((long double) * (l[i] - r2) / b); R = (r[i] - r2) / b;
      |                                ^~~~~~~~~~~~~
strange_device.cpp:101:33: error: no matching function for call to 'std::vector<std::array<long long int, 4> >::push_back(<brace-enclosed initializer list>)'
  101 |         if (r1 + 1 <= r2) pos.pb({r1 + 1, r2, L, R});
      |                           ~~~~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from strange_device.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<long long int, 4>; _Alloc = std::allocator<std::array<long long int, 4> >; std::vector<_Tp, _Alloc>::value_type = std::array<long long int, 4>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<long long int, 4>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<long long int, 4>; _Alloc = std::allocator<std::array<long long int, 4> >; std::vector<_Tp, _Alloc>::value_type = std::array<long long int, 4>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<long long int, 4> >::value_type&&' {aka 'std::array<long long int, 4>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
strange_device.cpp:103:32: error: invalid type argument of unary '*' (have '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'})
  103 |         L = ceil((long double) * (l[i] - (r2 + 1)) / b); R = (r[i] - (r2 + 1)) / b;
      |                                ^~~~~~~~~~~~~~~~~~~
strange_device.cpp:104:36: error: no matching function for call to 'std::vector<std::array<long long int, 4> >::push_back(<brace-enclosed initializer list>)'
  104 |         if (r2 + 1 <= b - 1) pos.pb({r2 + 1, b - 1, L, R});
      |                              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from /usr/include/c++/11/functional:62,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:65,
                 from strange_device.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<long long int, 4>; _Alloc = std::allocator<std::array<long long int, 4> >; std::vector<_Tp, _Alloc>::value_type = std::array<long long int, 4>]'
 1187 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1187:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<long long int, 4>&'}
 1187 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<long long int, 4>; _Alloc = std::allocator<std::array<long long int, 4> >; std::vector<_Tp, _Alloc>::value_type = std::array<long long int, 4>]'
 1203 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:1203:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<long long int, 4> >::value_type&&' {aka 'std::array<long long int, 4>&&'}
 1203 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~