Submission #245783

#	Time	Username	Problem	Language	Result	Execution time	Memory
245783		kenken714	Strange Device (APIO19_strange_device)	C++14	100 / 100	2312 ms	61168 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n, a, b, r;
vector<P> s;
bool ok = false;
ll gcd(ll a, ll b){
    return (b == 0 ? a : gcd(b, a % b));
}

ll f(ll a){
    ll res = a % r;
    if (res == 0) return r;
    return res;
}
void solve(ll a, ll b){
    ll c = (a + r - 1) / r * r;
    if(c > b){
        s.push_back(P(f(a), f(b)));
        return;
    }
    if(c - a + 1 == r){
        ok = true;
        return;
    }
    s.push_back(P(f(a), f(c)));
    if (c == b) return;
    solve(c + 1, b);
}
int main() {
    cin >> n >> a >> b;
    r = a / gcd(a, b + 1);
    if((ll)1e18 / r < b){
        ll ans = 0;
        REP(i, n){
            ll a, b;
            cin >> a >> b;
            ans += b - a + 1;
        }
        cout << ans << endl;
        return 0;
    }
    r *= b;
    REP(i, n){
        ll a, b;
        cin >> a >> b;
        solve(a, b);
    }
    if (ok){
       cout << r << endl;
       return 0;
    }
    ll ans = 0;
    sort(ALL(s));
    vector<P> t;
    t.push_back(P(MINF, MINF));
    REP(i, s.size()){
        //cout << s[i].first << " " << s[i].second << endl;
        if(t.back().second < s[i].first){
            t.push_back(s[i]);
            ans += s[i].second - s[i].first + 1;
        }
        else if(t.back().second < s[i].second){
            ans += s[i].second - t.back().second;
            t.back().second = s[i].second;
        }
    }
    cout << ans << endl;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:4:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i, n) for (ll i = 0; i < n; i++)
strange_device.cpp:69:9:
     REP(i, s.size()){
         ~~~~~~~~~~~                 
strange_device.cpp:69:5: note: in expansion of macro 'REP'
     REP(i, s.size()){
     ^~~

• 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