Submission #211605

#	Time	Username	Problem	Language	Result	Execution time	Memory
211605		devid	Strange Device (APIO19_strange_device)	C++17	100 / 100	808 ms	47552 KiB

strange_device

#pragma GCC optimize("Ofast,fast-math,unroll-loops")
 
#include <bits/stdc++.h>
 
#define int ll
//#define double long double
#define endl '\n'
#define all(C) (C).begin(), (C).end()
#define rall(C) (C).rbegin(), (C).rend()
#define mp make_pair 
#define pb emplace_back
#define dbg(x) cerr << #x << " : " << x << endl
//#define PI 3.141592653589
 
using namespace std;
        
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair <int, int>;
using pld = pair <ld, ld>;

/*
const ll MAX_MEM = 4e8;
char MEM[MAX_MEM];
ll MEM_POS = 0;
void* operator new(size_t x)
{
    auto ret = MEM + MEM_POS;
    MEM_POS += x;
    assert(MEM_POS < MAX_MEM);
    return ret;
}
void operator delete(void*)
{}
*/
        
template <class T>
istream& operator>> (istream &in, vector <T> &a)
{
    for (auto &i : a)
        in >> i;
    return in;
}
        
template <class T> 
ostream& operator<< (ostream &out, vector <T> a)
{
    for (auto &i : a)
        out << i << ' ';
    return out;
}
        
template <class T, class U>
istream& operator>> (istream &in, pair <T, U> &p)
{
    in >> p.first >> p.second;
    return in;
}
        
template <class T, class U>
ostream& operator<< (ostream &out, pair <T, U> p)
{
    out << p.first << " " << p.second << " ";
    return out;
}
        
inline void Start()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen("lol.in", "r", stdin);
    //freopen("lol.out", "w", stdout);
}

const int OPEN = 0, CLOSE = 1;
struct event
{
    int x, t;
    event() {}
    event(int x, int t) : x(x), t(t) {}
};

signed main()
{
    Start();
    int n, a, b;
    cin >> n >> a >> b;
    int k = a / gcd(a, b + 1);
    int t = k * b;
    vector <event> e;
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        if (l / t == r / t)
        {
            e.pb(l % t, OPEN);
            e.pb(r % t + 1, CLOSE);
            continue;
        }
        if (l / t + 1 == r / t)
        {
            if (r - l + 1 < t)
            {
                e.pb(l % t, OPEN);
                e.pb(t, CLOSE);
                e.pb(0, OPEN);
                e.pb(r % t + 1, CLOSE);
                continue;
            }
        }
        cout << t;
        return 0;
    }
    sort(all(e), [] (event a, event b) {return a.x < b.x || (a.x == b.x && a.t < b.t);});
    int lst = -1, bal = 0, ans = 0;
    for (auto f : e)
    {
        if (f.t == OPEN)
        {
            ++bal;
            if (bal == 1)
                lst = f.x;
        }
        else
        {
            --bal;
            if (!bal)
            {
                ans += f.x - lst;
            }
        }
    }
    cout << ans;
    return 0;
}

• 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