Submission #1227033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227033		feining_for_gm	Strange Device (APIO19_strange_device)	C++20	100 / 100	278 ms	17136 KiB

strange_device

#pragma GCC optimize("03")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for(auto &i: x) cerr << (f++? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x+= 0x9e3779b97f4a7c15;
        x = (x^(x>>30))*0xbf58476d1ce4e5b9;
        x = (x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rng();
        return splitmix64(x+FIXED_RANDOM);
    }
};

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using safe_set = unordered_set<T, custom_hash>;
template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;

const int MAX_N = 500005;
const int MAX_M = 8005;
const long long INF = 1000000000000000005;
const int MOD = 1000000007;

struct mint {
    int v;
    mint() :v(0) {}
    mint(long long x) {
        if(x >= 0) v = x%MOD;
        else {
            x %= MOD;
            if(x < 0) x += MOD;
            v = x;
        }
    }

    friend ostream& operator<<(ostream& stream, const mint& x) { stream << x.v; return stream; }
    friend istream& operator>>(istream& stream, mint& val) { int x; stream >> x; val.v = x >= 0 ? x%MOD : x+(-x+MOD-1)/MOD*MOD; return stream; }
    operator int()const { return v; }
    mint& operator++() { if(++v >= MOD)v-= MOD; return *this; }
    mint& operator--() { if(--v < 0)v+= MOD; return *this; }
    mint& operator+=(const mint& y) { v = v+y.v-((v+y.v) >= MOD ? MOD : 0); return *this; }mint operator+(const mint& y)const { mint x = *this; return x+= y; }
    mint& operator-=(const mint& y) { v = v-y.v+(v-y.v < 0 ? MOD : 0); return *this; }mint operator-(const mint& y)const { mint x = *this; return x-= y; }
    mint& operator*=(const mint& y) { v = ((long long)v*y.v)%MOD; return *this; }mint operator*(const mint& y)const { mint x = *this; return x *= y; }
    mint& operator%=(const mint& y) { if(y.v)v %= y.v; return *this; }mint operator%(const mint& y)const { mint x = *this; return x %= y; }
    mint& operator/=(const mint& y) { return *this *= ModInverse(y.v); }mint operator/(const mint& y)const { return *this*ModInverse(y.v); }
    mint& operator^=(const mint& y) { *this = this->Pow(y); return *this; }mint Pow(int y)const { mint r = 1, x = v; for(y <<= 1; y >>= 1; x = x*x)if(y & 1)r = r*x; return r; }
    mint ModInverse(int a)const { return mint(a) ^ (MOD-2); }
    friend mint operator+(const mint& a, long long b) { return a+mint(b); }friend mint operator+(long long a, const mint& b) { return mint(a)+b; }friend mint operator+(const mint& a, int32_t b) { return a+mint(b); }friend mint operator+(int32_t a, const mint& b) { return mint(a)+b; }
    friend mint operator-(const mint& a, long long b) { return a-mint(b); }friend mint operator-(long long a, const mint& b) { return mint(a)-b; }friend mint operator-(const mint& a, int32_t b) { return a-mint(b); }friend mint operator-(int32_t a, const mint& b) { return mint(a)-b; }
    friend mint operator*(const mint& a, long long b) { return a*mint(b); }friend mint operator*(long long a, const mint& b) { return mint(a)*b; }friend mint operator*(const mint& a, int32_t b) { return a*mint(b); }friend mint operator*(int32_t a, const mint& b) { return mint(a)*b; }
    friend mint operator/(const mint& a, int32_t b) { return a/mint(b); }friend mint operator/(int32_t a, const mint& b) { return mint(a)/b; }friend mint operator/(const mint& a, long long b) { return a/mint(b); }friend mint operator/(long long a, const mint& b) { return mint(a)/b; }
    friend mint operator^(const mint& a, long long b) { return a.Pow(b); }friend mint operator^(long long a, const mint& b) { return mint(a).Pow(b); }friend mint operator^(const mint& a, int32_t b) { return a.Pow(b); }friend mint operator^(int32_t a, const mint& b) { return mint(a).Pow(b); }friend mint operator^(const mint& a, const mint& b) { return a.Pow(b); }
    bool operator==(const mint& y)const { return v == y.v; }bool operator==(int32_t y)const { return v == y; }bool operator==(long long y)const { return v == y; }
    bool operator!=(const mint& y)const { return v != y.v; }bool operator!=(int32_t y)const { return v != y; }bool operator!=(long long y)const { return v != y; }
    bool operator>(const mint& y)const { return v > y.v; }bool operator>(int32_t y)const { return v > y; }bool operator>(long long y)const { return v > y; }
    bool operator>=(const mint& y)const { return v >= y.v; }bool operator>=(int32_t y)const { return v >= y; }bool operator>=(long long y)const { return v >= y; }
    bool operator<(const mint& y)const { return v < y.v; }bool operator<(int32_t y)const { return v < y; }bool operator<(long long y)const { return v < y; }
    bool operator<=(const mint& y)const { return v <= y.v; }bool operator<=(int32_t y)const { return v <= y; }bool operator<=(long long y)const { return v <= y; }

    mint pow(long long e) const {
        mint base = *this, res = 1;
        while(e) {
            if(e & 1) res *= base;
            base *= base;
            e >>= 1;
        }
        return res;
    }
    mint inv() const { return this->pow(MOD-2); }
};

void solve() {
    int n; long long a, b;
    cin >> n >> a >> b;

    a /= __gcd(a, b+1);

    __int128 tot = (__int128)a*b;
    vector<pair<long long, long long>> segments;
    for(int i = 0; i < n; ++i) {
        long long l, r;
        cin >> l >> r;

        if(r-l+1 >= tot) segments.push_back({0LL, tot-1LL});
        else {
            long long lmod = l%tot, rmod = r%tot;
            if(lmod <= rmod) segments.push_back({lmod, rmod});
            else {
                segments.push_back({lmod, tot-1});
                segments.push_back({0, rmod});
            }
        }
    }

    sort(segments.begin(), segments.end());
    int m = segments.size();
    long long cl = segments[0].first, cr = segments[0].second, ans = 0;
    for(int i = 1; i < m; ++i) {
        if(segments[i].first <= cr) cr = max(cr, segments[i].second);
        else {
            ans += (cr-cl+1);
            cl = segments[i].first;
            cr = segments[i].second;
        }
    }

    ans += cr-cl+1;
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

/* Lucky cat
*    /\_/\
*   (= ._.)
*   / >  \>
*/

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 30 / 30