Submission #363995

#	Time	Username	Problem	Language	Result	Execution time	Memory
363995		erfanmir	Strange Device (APIO19_strange_device)	C++17	100 / 100	1163 ms	171296 KiB

strange_device

// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 2e6 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 2e18 + 10;

ll n, val[MAXN];
ll A, B, ans, l[MAXN], r[MAXN];
vector<ll> vec;
vector<pll> seg;
unordered_map<ll, ll> um;

int main()
{
    um.max_load_factor(0.13);
    scanf("%lld %lld %lld", &n, &A, &B);
    for(ll i = 1; i <= n; i++){
        scanf("%lld %lld", l + i, r + i);
    }
    ll x = A / __gcd(A, B + 1);
    if(x > INF / B){
        for(ll i = 1; i <= n; i++){
            ans += r[i] - l[i] + 1;
        }
        printf("%lld\n", ans);
        return 0;
    }
    x *= B;
    vec.push_back(0);
    vec.push_back(x);
    for(ll i = 1; i <= n; i++){
        if(r[i] - l[i] + 1 >= x){
            printf("%lld\n", x);
            return 0;
        }
        ll L = l[i], R = r[i];
        L %= x;
        R %= x;
        vec.push_back(L);
        vec.push_back(R + 1);
        if(L > R){
            seg.push_back(mp(L, x - 1));
            seg.push_back(mp(0, R));
        }
        else{
            seg.push_back(mp(L, R));
        }
    }
    sort(all(vec));
    vec.erase(unique(all(vec)), vec.end());
    for(int i = 0; i < (int)vec.size(); i++){
        um[vec[i]] = i;
    }
    for(auto v : seg){
        ll ind1;
        ll ind2;
        ind1 = um[v.F];
        ind2 = um[v.S + 1];
        val[ind1]++;
        val[ind2]--;
    }
    for(ll i = 1; i < (ll)vec.size(); i++){
        val[i] += val[i - 1];
    }
    for(ll i = 0; i < (ll)vec.size() - 1; i++){
        if(val[i]){
            ans += vec[i + 1] - vec[i];
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

strange_device.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
strange_device.cpp: In function 'int main()':
strange_device.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%lld %lld %lld", &n, &A, &B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%lld %lld", l + i, r + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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