Submission #265284

#	Time	Username	Problem	Language	Result	Execution time	Memory
265284		Hideo	Strange Device (APIO19_strange_device)	C++11	100 / 100	584 ms	44668 KiB

strange_device

//1610612741, 1000000007
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define all(s) s.begin(), s.end()
#define ok puts("ok")
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define pi pair < int, int >
#define pii pair < int, pi >
#define next next123
#define left left123

const int N = 1e6 + 7;
const int INF = 1e9 + 7;

int n;
ll A, B, p, ans;
ll bound = 1e18;
bool trigger = false;

vector < pair < ll, ll > > s;

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> A >> B;
    p = A / __gcd(B + 1, A);
    if (B > bound / p)
        p = bound;
    else
        p *= B;
    for (int i = 1; i <= n; i++){
        ll l, r;
        cin >> l >> r;
        if (r - l + 1 >= p)
            trigger = true;
        l %= p;
        r %= p;
        if (l > r){
            s.pb({l, p - 1});
            s.pb({0, r});
        }
        else
            s.pb({l, r});
    }
    if (trigger){
        cout << p;
        return 0;
    }
    sort(all(s));
    ll r = -1;
    for (auto it : s){
        if (r < it.fr)
            r = it.fr - 1;
        ans += max(0LL, it.sc - r);
        r = max(r, it.sc);
    }
    cout << ans << endl;
}

Compilation message (stderr)

strange_device.cpp:34:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main(){
      |      ^

• 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