Submission #210034

#	Time	Username	Problem	Language	Result	Execution time	Memory
210034		gratus907	Strange Device (APIO19_strange_device)	C++17	100 / 100	763 ms	100412 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
#define int __int128
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = false;
std::ostream&operator<<( std::ostream& dest, __int128_t value )
{
    std::ostream::sentry s( dest );
    if ( s ) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[ 128 ];
        char* d = std::end( buffer );
        do
        {
            -- d;
            *d = "0123456789"[ tmp % 10 ];
            tmp /= 10;
        } while ( tmp != 0 );
        if ( value < 0 ) {
            -- d;
            *d = '-';
        }
        int len = std::end( buffer ) - d;
        if ( dest.rdbuf()->sputn( d, len ) != len ) {
            dest.setstate( std::ios_base::badbit );
        }
    }
    return dest;
}
int n, a, b;
int period;
vector <pii> v;
vector <pii> range;
int32_t main()
{
    usecppio
    ll _n, _a, _b;
    cin >> _n >> _a >> _b;
    n = _n, a = _a, b = _b;
    period = (a/(__gcd(a, b+1)))*b;
    for (int i = 0; i<n; i++)
    {
        ll l, r; cin >> l >> r;
        v.push_back({l, r});
        if (r - l + 1 >= period)
        {
            cout << period << '\n';
            return 0;
        }
        if (l%period <= r%period)
        {
            range.push_back({l%period, r%period});
        }
        else
        {
            range.push_back({0, r%period});
            range.push_back({l%period, period-1});
        }
    }
    sort(all(range));
    int start = range[0].first;
    int end = range[0].second;
    int ans = 0;
    for (int i = 1; i<range.size(); i++)
    {
        if (range[i].first > end)
        {
            ans += end-start+1;
            start = range[i].first;
            end = range[i].second;
        }
        else
            end = max(end, range[i].second);
    }
    ans += end-start+1;
    cout << ans << '\n';
}

• 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