Submission #1134780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134780		Nelt	Strange Device (APIO19_strange_device)	C++17	20 / 100	519 ms	110008 KiB

strange_device

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
map<ll, vector<pair<ll, ll>>> mp;
vector<pair<ll, ll>> all;
ll a, b;
void add_range(ll l, ll r)
{
    if (l > r) return;
    if (l / b == r / b)
    {
        mp[l / b % a].push_back(make_pair(l % b, r % b));
        return;
    }
    if (l % b == 0 and r % b == b - 1)
    {
        all.push_back(make_pair(l / b, r / b));
        return;
    }
    ll x = (l + b - 1) / b * b, y = r / b * b;
    add_range(l, x - 1);
    add_range(x, y - 1);
    add_range(y, r);
}
void Merge(vector<pair<ll, ll>> &v)
{
    sort(v.begin(), v.end());
    vector<pair<ll, ll>> nv;
    ll last = -1;
    for (auto [l, r] : v)
        if (max(l, last + 1) <= r)
        {
            nv.push_back(make_pair(max(l, last + 1), r));
            last = r;
        }
    v = nv;
}
bool contains(ll x)
{
    ll pos = upper_bound(all.begin(), all.end(), make_pair(x, (ll)2e18)) - all.begin();
    if (pos == 0) return false;
    pos--;
    if (all[pos].second < x) return false;
    return true;
}
void solve()
{
    ll n;
    cin >> n >> a >> b;
    a /= gcd(a, b + 1);
    while (n--)
    {
        ll l, r;
        cin >> l >> r;
        add_range(l, r);
    }
    Merge(all);
    ll ans = 0;
    for (auto [l, r] : all) ans += (r - l + 1) * b;
    for (auto [x, v] : mp)
    if (!contains(x))
    {
        Merge(v);
        for (auto [l, r] : v) ans += r - l + 1;
    }
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30