Submission #976825

#	Time	Username	Problem	Language	Result	Execution time	Memory
976825		Nahian9696	Strange Device (APIO19_strange_device)	C++17	5 / 100	2051 ms	142028 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;



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


using namespace __gnu_pbds;


template<typename dataType>
using ordered_set = tree<dataType, null_type, less<dataType>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename dataType1, typename dataType2>
using ordered_map = tree<dataType1, dataType2, less<dataType1>, rb_tree_tag, tree_order_statistics_node_update>;





typedef long double                         ld;
typedef unsigned                            ui;
typedef long long                           lli;
typedef unsigned long long                  ulli;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<ui>                          vui;
typedef vector<lli>                         vlli;
typedef vector<ulli>                        vulli;
typedef list<int32_t>                       lsi;
typedef list<ld>                            lsld;
typedef list<ui>                            lsui;
typedef list<lli>                           lslli;
typedef list<ulli>                          lsulli;
typedef set<int32_t>                        si;
typedef set<ld>                             sld;
typedef set<ui>                             sui;
typedef set<lli>                            slli;
typedef set<ulli>                           sulli;

typedef pair<lli, lli>                      pii;
typedef pair<lli, lli>                      pll;



#define int                                 int64_t

#define endl                                "\n"
#define inp(n)                              int n; cin >> n
#define Inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           int a,b; cin >> a >> b
#define Inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second
#define maxi                                maximize
#define mini                                minimize   

#define yes                                 cout << "yes" << endl
#define no                                  cout << "no" << endl
#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)




template<typename dataType1>
inline void print(dataType1 a) {cout << a << endl;}
template<typename dataType1, typename dataType2>
inline void print(dataType1 a, dataType2 b) {cout << a << " " << b << endl;}
template<typename dataType1, typename dataType2, typename dataType3>
inline void print(dataType1 a, dataType2 b, dataType3 c) {cout << a << " " << b << " " << c << endl;}
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
inline void print(dataType1 a, dataType2 b, dataType3 c, dataType4 d) {cout << a << " " << b << " " << c << " " << d << endl;}
template<typename dataType>
inline void printarr(dataType* arr, int32_t n) {f0(i,n) cout << arr[i] << " "; cout << endl;}
template<typename dataType>
inline dataType abs(dataType k) {if (k >= 0) return k; else return (-k);}
template<typename dataType>
inline bool isEqual(dataType a, dataType b) {return (abs((dataType)(a-b)) < 1e-9);}
template<typename dataType>
inline void maximize(dataType &a, dataType b) {if (a < b) a = b;}
template<typename dataType>
inline void minimize(dataType &a, dataType b) {if (a > b) a = b;}

template<typename dataType>
dataType partitionProbDiff(dataType* arr, dataType n) {
    dataType sum = 0;
    for (int32_t i = 0; i < n; i++) sum += arr[i];

    bool dp[n + 1][sum + 1];
    for (int32_t i = 0; i <= n; i++) dp[i][0] = true;
    for (int32_t i = 1; i <= sum; i++) dp[0][i] = false;

    for (int32_t i = 1; i <= n; i++) {
        for (int32_t j = 1; j <= sum; j++) {
            dp[i][j] = dp[i - 1][j];
 
            if (arr[i - 1] <= j)
                dp[i][j] |= dp[i - 1][j - arr[i - 1]];
        }
    }
    for (int32_t j = sum / 2; j >= 0; j--) {
        if (dp[n][j] == true) {
            return (sum - 2 * j);
        }
    }
}
template<typename dataType>
bool subsetSumProblem(dataType set[], dataType n, dataType sum) {
    bool subset[n + 1][sum + 1];
    for (int32_t i = 0; i <= n; i++)
        subset[i][0] = true;
    for (int32_t i = 1; i <= sum; i++)
        subset[0][i] = false;
    for (int32_t i = 1; i <= n; i++) {
        for (int32_t j = 1; j <= sum; j++) {
            if (j < set[i - 1])
                subset[i][j] = subset[i - 1][j];
            if (j >= set[i - 1])
                subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
        }
    }
    return subset[n][sum];
}
bool isPrefix(string &s, string &y) {
    if(s.length() > y.length()) return false;
    f0(i, s.length()) if(s[i] != y[i]) return false;
    return true;
}
bool ispalindrom(string s) {
    f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
    return true;
}

template<typename dataType>
dataType gcd(dataType a, dataType b) {
    while (b != 0) {
        dataType c = b;
        b = (lli)a % (lli)b;
        a = c;
    }
    return a;
}


template<typename dataType>
void allPrimeBoolArray(dataType n, bool* prime) {
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
}
template<typename dataType1, typename dataType2>
void allPrimeVector(dataType1 n, dataType2 &primeList) {
    bool prime[n+1];
    memset(prime, true, sizeof(prime));

    for (int32_t p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (dataType1 i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }

    for (int32_t p = 2; p <= n; p++)
        if (prime[p])
            primeList.pb(p);
}

template<typename dataType>
string decimalTokbitsBinary(dataType n,dataType k) {
    string s = bitset<64>(n).to_string();

    return s.substr(64-k);
}

template<typename dataType>
string decimalToBinary(dataType n) {
    string s = bitset<64>(n).to_string();

    const auto loc1 = s.find('1');

    if(loc1 != string::npos)
        return s.substr(loc1);
     
    return "0";
}

template<typename dataType>
dataType val(char c) {
    if (c >= '0' && c <= '9')
        return (dataType)c - '0';
    else
        return (dataType)c - 'A' + 10;
}
template<typename dataType>
dataType nthBaseToDecimal(string str, dataType base) {
    int32_t len = str.length();
    int32_t power = 1;
    dataType num = 0;
 
    for (int32_t i = len - 1; i >= 0; i--) {
        num += (val<dataType>(str[i]) * power);
        power *= base;
    }

    return num;
}

template<typename dataType>
char reVal(dataType num) {
    if (num >= 0 && num <= 9)
        return (char)(num + '0');
    else
        return (char)(num - 10 + 'A');
}
template<typename dataType>
string nthBasefromDeci(dataType inputNum, dataType base) {
    string res = "";
    while (inputNum > 0) {
        res += reVal(inputNum % base);
        inputNum /= base;
    }
    if (res == "")
        res = "0";
    return revStr(res);
}


template<typename dataType1, typename dataType2>
dataType1 smallFactor(dataType1 n, dataType2 &primes) {
    for (dataType1 x:primes) {
        if(n % x == 0) {
            return x;
            break;
        } else if (x > sqrt(n)) {
            return n;
            break;
        }
    }
    return 7;
}

template<typename dataType>
dataType phi(dataType n) {
    dataType result = n;
    for(int32_t p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t powMod(dataType1 base, dataType2 n, dataType3 mod) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        int64_t t_pow = (int64_t)powMod(base, n/2, mod);
        return ((t_pow*t_pow) % mod);
    }
    int64_t t_pow = (int64_t)powMod(base, (n-1)/2, mod);
    return ((int64_t)base * ((t_pow*t_pow) % mod) % mod);
}
template<typename dataType1, typename dataType2>
int64_t modInverse(dataType1 n, dataType2 mod, bool isPrime = true) {
    if(isPrime) return powMod(n, mod-2, mod);
    return powMod(n, phi(mod)-1, mod);
}
template<typename dataType1, typename dataType2, typename dataType3>
int64_t modDivide(dataType1 a, dataType2 b, dataType3 mod, bool isPrime = true) {
    return (((int64_t)a * modInverse(b, mod, isPrime)) % mod);
}

//define a compare function for pair
template<typename dataType1, typename dataType2, typename dataType3, typename dataType4>
bool compare(pair<dataType1, dataType2> &a, pair<dataType3, dataType4> &b) {
    return a.first < b.first;
}


template<typename dataType>
dataType segtree_operator(dataType a, dataType b) {
    return a + b;
}


template<typename dataType>
struct segtree {
    int size;
    vector<dataType> tree;
    dataType init_val;
    
    template<typename dataType1>
    segtree(int n, dataType1 &arr, dataType init) {
        init_segtree(n, init);
        for (int32_t i = 0; i < n; i++) {
            tree[size+i] = arr[i];
        }
        for (int32_t i = size-1; i > 0; i--) {
            tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
        }
    }

    segtree(int n, dataType* arr, dataType init) {
        init_segtree(n, init);
        for (int32_t i = 0; i < n; i++) {
            tree[size+i] = arr[i];
        }
        for (int32_t i = size-1; i > 0; i--) {
            tree[i] = segtree_operator(tree[i*2], tree[i*2+1]);
        }
    }

    void init_segtree(int n, dataType init) {
        size = 1;
        init_val = init;
        while (size < n) size *= 2;
        tree.resize(size*2, init_val);
    }

    void update(int ind, dataType val) {
        ind += size;
        tree[ind] = val;
        while (ind > 1) {
            ind /= 2;
            tree[ind] = segtree_operator(tree[ind*2], tree[ind*2+1]);
        }
    }

    dataType query(int l, int r) {
        l += size;
        r += size;
        dataType res = init_val;
        while (l <= r) {
            if (l % 2 == 1) res = segtree_operator(res, tree[l]);
            if (r % 2 == 0) res = segtree_operator(res, tree[r]);
            l = (l+1) / 2;
            r = (r-1) / 2;
        }
        return res;
    }
};

// Varriables & helper functions
int n;

int a, b, t;
set<pair<int,int>> ranges_lr, ranges_rl;
vector<pair<int,int>> ranges;
pair<int, int> process(int x, int y) {
    x %= t;
    y %= t;

    return {x, y};
}

// Solver functions

int32_t solve1(int32_t) {
    cin >> n >> a >> b;

    int k = a/gcd(a, b+1);

    if(ld(b) * ld(k) >= 2e18) {
        t = 2e18;
    } else t = b*k;

    // print(t);

    f0(i, n) {
        inp2(x, y);
        if(y - x >= t) {
            print(t);
            finish;
        }
        auto [l, r] = process(x, y);
        // print(l, r);
        if(l > r) {
            ranges_lr.insert({l, t});
            ranges_lr.insert({0, r});
            ranges_rl.insert({t, l});
            ranges_rl.insert({r, 0});
            ranges.pb({l, t});
            ranges.pb({0, r});
        } else {
            ranges_lr.insert({l, r});
            ranges_rl.insert({r, l});
            ranges.pb({l, r});
        }
    }
    asrt(ranges);

    for(auto [l, r]:ranges) {
        // print(l, r);
        if(ranges_lr.find({l, r}) == ranges_lr.end()) {
            continue;
        }

        set<pair<int,int>> temp;

        while(true) {
            bool have_l = true, have_r = true;
            auto it = ranges_lr.lower_bound({l, -INF});
            int cnt = 0;
            while(it != ranges_lr.end()) {
                if(it->first > r) {
                    break;
                }
                cnt++;
                maxi(r, it->second);
                temp.insert(*it);
                it++;
            }
            if(cnt == 0) {
                have_l = false;
            }

            it = ranges_rl.lower_bound({l, -INF});
            cnt = 0;
            while(it != ranges_rl.end()) {
                if(it->first > r) {
                    break;
                }
                cnt++;
                mini(l, it->second);
                temp.insert({it->second, it->first});
                it++;
            }
            if(cnt == 0) {
                have_r = false;
            }

            if(!have_l && !have_r) {
                break;
            }

            for(auto [ll, rr]:temp) {
                ranges_lr.erase({ll, rr});
                ranges_rl.erase({rr, ll});
            }
            temp.clear();
        }
        
        ranges_lr.insert({l, r});
        ranges_rl.insert({r, l});
    }

    int ans = 0;

    for(auto [l, r]:ranges_lr) {
        ans += r - l+1;
    }

    print(min(ans, t));
    finish;
}


int32_t solve2(int32_t);


int32_t solve3(int32_t);



int32_t main() {

    #if defined __has_include
        #if __has_include("LOCAL.hh")
            #include "LOCAL.hh"
        #endif
    #endif

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        // freopen("output.txt", "w", stdout);
        using namespace std::chrono;
        cout << fixed << setprecision(9);
        auto begin = steady_clock::now();
    #else
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif

    // Previous code



    // Main code
    int32_t test = 1;

    // testIn;

    tests {

        solve1(testNo);

    }
    #ifdef LOCAL
        auto end = steady_clock::now();
        cout << "\nTime : " 
             << (ld)duration_cast<nanoseconds>
                (end - begin).count()/1000000000 
             << "s" << endl;
    #endif
    finish;
}

Compilation message (stderr)

strange_device.cpp: In function 'bool isPrefix(std::string&, std::string&)':
strange_device.cpp:59:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 | #define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
      |                                                                  ^
strange_device.cpp:168:5: note: in expansion of macro 'f0'
  168 |     f0(i, s.length()) if(s[i] != y[i]) return false;
      |     ^~
strange_device.cpp: In function 'bool ispalindrom(std::string)':
strange_device.cpp:59:66: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 | #define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
      |                                                                  ^
strange_device.cpp:172:5: note: in expansion of macro 'f0'
  172 |     f0(i, s.length()/2) if(s[i] != s[s.length()-i-1]) return false;
      |     ^~

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