Submission #134049

#	Time	Username	Problem	Language	Result	Execution time	Memory
134049		ksmzzang2003	Strange Device (APIO19_strange_device)	C++17	100 / 100	728 ms	17824 KiB

strange_device

#define DEBUG
// #define FASTIO
 
#include <cstring>
#include <cassert>
#include <utility>
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <bitset>
#include <chrono>
#include <cstdlib>
#include <functional>
#include <tuple>
#include <climits>
#include <limits>
#include <deque>
#include <list>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <complex>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
 
#define F first
#define S second 
#define pb push_back
#define endl "\n"
 
#ifdef FASTIO
 
#define pr(x) printf("%d", x)
#define ps    printf(" ")
#define endc  printf("\n")
#define pl(x) printf("%lld", x)
#define pf(x) printf("%lf", x)
#define sc(x) scanf("%d", &x)
#define sl(x) scanf("%lld", &x)
#define sf(x) scanf("%lf", &x)
#define IOS 
 
#endif
 
#ifndef FASTIO
    #define IOS { ios :: sync_with_stdio(false); cin.tie(0); }
#endif
 
#ifdef DEBUG
    #define dbg(s) {s;}
#endif
 
#ifndef DEBUG
    #define dbg(s)
#endif
 
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int grand(int x) { // from [0, n-1]
    return uniform_int_distribution<int>(0, x - 1)(rng);
}
 
#define int ll
#define i32 int32_t
#define all(v) (v).begin(),(v).end()
 
typedef long long ll;
typedef long double ld;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
 
inline string ps(pii z) {
    stringstream ss; ss << "[" << z.F << ", " << z.S << "]";
    return ss.str();
}
 
ll gcd(ll x, ll y) {
    if (x < y) return gcd(y, x);
    if (y == 0) return x;
    return gcd(y, x % y);
} 
 
const ll mod = 1e9 + 7;
 
ll modexp(ll x, ll ex) {
    ll ans = 1ll;
    while (ex > 0) {
        if (ex & 1ll) ans = (ans * x) % mod;
        ex >>= 1ll;
        x = (x * x) % mod;
    }
    return ans;
}
 
const int maxn = 1e6 + 7;
 
const ll inf = 1e18 + 7;
 
vector < pii > v;
 
i32 main() {
    //freopen("<file>.in", "r", stdin);
    //freopen("<file>.out", "w", stdout);
 
    IOS;
    
    int n, A, B; cin >> n >> A >> B;
    int g = gcd(A, B + 1); A /= g;
    if (A >= inf / B) A = inf;
    else A *= B;
 
    for (int j = 1; j <= n; j++) {
        int l, r; cin >> l >> r;
        if (r - l >= A) {
            cout << A << endl; return 0;
        }
        if (l <= A * (r / A)) {
            v.pb({0, r % A});
            if (l < A * (r / A))
                v.pb({l % A, A - 1});
        } else {
            v.pb({l % A, r % A});
        }
    }
 
    sort(all(v));
    
    int ans = 0;
 
    for (int j = 0; j < v.size(); ) {
        int i = j; pii ci = v[j];
        while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
            i++; ci.S = max(ci.S, v[i].S);
        }
        j = i + 1;
        ans += ci.S - ci.F + 1;
    }
    cout << ans << endl;
}

Compilation message (stderr)

strange_device.cpp: In function 'int32_t main()':
strange_device.cpp:137:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < v.size(); ) {
                     ~~^~~~~~~~~~
strange_device.cpp:139:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i + 1 < v.size() && v[i + 1].F <= ci.S) {
                ~~~~~~^~~~~~~~~~

• 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