Submission #143019

#	Time	Username	Problem	Language	Result	Execution time	Memory
143019		karma	Strange Device (APIO19_strange_device)	C++11	100 / 100	712 ms	19224 KiB

strange_device

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long long
#define Debug(x)      cerr << #x << "is " << x << '\n';
#define pb            emplace_back
#define mp            make_pair
#define x             first
#define y             second
//#define LuckyAurora
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

typedef pair<int, int> pii;
const int N = int(1e6) + 1;

struct TIrene {
    ll l, r;
    TIrene(ll l = 0, ll r = 0): l(l), r(r) {}
    bool operator<(const TIrene& o)const& {
        return l < o.l || (l == o.l && r < o.r);
    }
};
vector<TIrene> v;
int n;
ll A, B, l, r, irene, Irene, low, high, res;
const ll inf = (ll)1e18;

// A / GCD(A, B + 1) * B

ll GCD(ll a, ll b)
{
    ll r;
    if(a < b) swap(a, b);
    while(b) {
        r = a % b;
        a = b, b = r;
    }
    return a;
}

ll Pos(ll x)
{
    if(inf >= Irene) return x % Irene;
    return x;
}

void Enter()
{
     cin >> n >> A >> B;
     irene = A / GCD(A, B + 1);
     Irene = LLONG_MAX;
     if(inf / irene >= B) Irene = B * irene;
     for(int i = 0; i < n; ++i) {
        cin >> l >> r;
        if(r - l + 1 >= Irene) {cout << Irene; exit(0);}
        low = Pos(l), high = Pos(r);
        //cout << low << ' ' << high << '\n';
        if(high >= low) v.pb(low, high);
        else v.pb(low, Irene - 1), v.pb(0, high);
     }
     sort(v.begin(), v.end());
}

void Solve()
{
     res = 0, high = -2, low = -1;
     for(int i = 0; i < int(v.size()); ++i) {
        if(v[i].l > high) {
            res += high - low + 1;
            low = v[i].l, high = v[i].r;
        } else high = max(high, v[i].r);
     }
     res += high - low + 1;
     cout << res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(FileName".inp", "r")) {
        freopen(FileName".inp", "r", stdin);
        freopen(FileName".out", "w", stdout);
    }

    /*int nTest; cin >> nTest;
    while(nTest --)*/ Enter(), Solve();

    return 0;
}

Compilation message (stderr)

strange_device.cpp:15:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
strange_device.cpp: In function 'int main()':
strange_device.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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