Submission #1157738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157738		MPG	Strange Device (APIO19_strange_device)	C++20	35 / 100	302 ms	16956 KiB

strange_device

#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimization ("O1, O2, O3, Ofast")
//#pragma GCC optimization ("trapv")
//#pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")



#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("txt.in.5", "r", stdin); freopen("out1.txt", "w", stdout);
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;



ll const maxn = 1e5 + 123;
ll const inf = 1e18 + 10;
ll const loG = 23;
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 350;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}





ll n, a, b, k, ans;
//set <pair <ll, ll>> st;
vector <pair <ll, ll>> arr;








int main(){
sariE;// filE;

cin >> n >> a >> b;
k = a / __gcd(a, (b + 1));
k = k * b;
//cout << k << endl;



//cout << "k is " << k << endl;


for (int i = 1; i < n + 1; i++){
    ll l, r; cin >> l >> r;
    if (r - l + 1 > k)
        arr.push_back({0, k - 1});
    else{
        ll baz1 = l % k, baz2 = r % k;
        //cout << "baze ha " << baz1 << ' ' << baz2 << endl;
        if (baz1 <= baz2){
            arr.push_back({baz1, baz2});
            //setter(baz1, baz2 + 1, 1, 0, 0, inf);
        }
        else{
            arr.push_back({baz1, k - 1});
            arr.push_back({0, baz2});
            //setter(baz1, k, 1, 0, 0, inf);
            //setter(0, baz2 + 1, 1, 0, 0, inf);
        }
        
    }
    //for (ll j = l; j <= r; j++)
    //     st.insert({f1(j), f2(j)});
}
sort(arr.begin(), arr.end());
ll mx = arr[0].second; ans += mx - arr[0].first + 1;
//cout << "mx is " << mx << endl;
//cout << arr[0].first << ' ' << arr[0].second << endl;
for (int i = 1; i < arr.size(); i++){
    auto p = arr[i];
    //cout << "mx is " << mx << endl;
    //cout << p.first << ' ' << p.second << endl;
    if (mx < p.first){
        //cout << "A " << mx << endl;
        ans += p.second - p.first + 1;
        mx = p.second;
        continue;
    }
    if (p.first <= mx && mx < p.second){
        //cout << "B " << mx << endl;
        ans += p.second - mx;
        mx = p.second;
        continue;
    }
}
cout << ans << endl;


// //cout << st.size() << endl;











}

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