oj.uz

답안 #976814

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
976814 2024-05-07T06:58:06 Z Nahian9696 이상한 기계 (APIO19_strange_device) C++17
55 / 100
 2220 ms 160464 KB 
#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;
    if(x > y) 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) >= 1e18) {
        t = 1e18;
    } 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);
        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(ans);
    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

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 11 ms 1752 KB Output is correct
3 Correct 11 ms 1752 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1821 ms 141724 KB Output is correct
3 Correct 1961 ms 159852 KB Output is correct
4 Correct 2069 ms 160144 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1821 ms 141724 KB Output is correct
3 Correct 1961 ms 159852 KB Output is correct
4 Correct 2069 ms 160144 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1933 ms 159900 KB Output is correct
7 Correct 1967 ms 159916 KB Output is correct
8 Correct 1906 ms 160384 KB Output is correct
9 Correct 2220 ms 159960 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1821 ms 141724 KB Output is correct
3 Correct 1961 ms 159852 KB Output is correct
4 Correct 2069 ms 160144 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 120 ms 16368 KB Output is correct
7 Correct 138 ms 16688 KB Output is correct
8 Correct 133 ms 16460 KB Output is correct
9 Correct 154 ms 16576 KB Output is correct
10 Correct 123 ms 16424 KB Output is correct
11 Correct 124 ms 16572 KB Output is correct
12 Correct 136 ms 16436 KB Output is correct
13 Correct 166 ms 16572 KB Output is correct
14 Correct 141 ms 16360 KB Output is correct
15 Correct 176 ms 16572 KB Output is correct
16 Correct 176 ms 16572 KB Output is correct
17 Correct 155 ms 16384 KB Output is correct
18 Correct 1840 ms 160060 KB Output is correct
19 Correct 1980 ms 160276 KB Output is correct
20 Correct 2193 ms 160464 KB Output is correct
21 Correct 143 ms 16428 KB Output is correct
22 Correct 144 ms 16576 KB Output is correct
23 Correct 136 ms 16844 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 169 ms 14424 KB Output is correct
3 Correct 174 ms 16576 KB Output is correct
4 Correct 2062 ms 159964 KB Output is correct
5 Correct 182 ms 16576 KB Output is correct
6 Correct 174 ms 16444 KB Output is correct
7 Correct 174 ms 16488 KB Output is correct
8 Correct 190 ms 16516 KB Output is correct
9 Correct 167 ms 16572 KB Output is correct
10 Correct 143 ms 16360 KB Output is correct
11 Correct 175 ms 16376 KB Output is correct
12 Correct 149 ms 16524 KB Output is correct
13 Correct 175 ms 16392 KB Output is correct
14 Correct 2214 ms 160176 KB Output is correct
15 Correct 129 ms 16576 KB Output is correct
16 Correct 1800 ms 160140 KB Output is correct
17 Correct 1787 ms 160064 KB Output is correct
18 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 11 ms 1752 KB Output is correct
3 Correct 11 ms 1752 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -