Submission #1206024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206024		ender_shayan	Strange Device (APIO19_strange_device)	C++17	20 / 100	1208 ms	589824 KiB

strange_device

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;
typedef __uint128_t     UL;

// find_by_order             order_of_key

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#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 lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <pii, vector<pii>, greater<pii>>




ll inf=1e18+100;
const int N=(1e6+10)*60;
int n,m,k,q,nn;

ll c,a,b;
ll seg[N];
pii nxt[N];
void upd(ll lx,ll rx,ll l=0,ll r=c,ll v=1){
    if(seg[v]==r-l)return;
    if(lx<=l && r<=rx){
        seg[v]=r-l;
        return;
    }
    ll mid=(l+r)>>1;
    if(lx<mid){
        if(nxt[v].F==0)
            nxt[v].F=++nn;
        upd(lx,rx,l,mid,nxt[v].F);
    }
    if(rx>mid){
        if(nxt[v].S==0)
            nxt[v].S=++nn;
        upd(lx,rx,mid,r,nxt[v].S);
    }
    seg[v]=seg[nxt[v].F]+seg[nxt[v].S];
}
int main(){
    fast_io
    nn=1;
    cin>>n>>a>>b;
    UL tmp=a/__gcd(a,b+1)*b;
    if(tmp>inf)c=inf;
    else c=tmp;
    for1(n){
        ll l,r;cin>>l>>r;
        if(r-l>=c)
            return cout<<c<<endl,0;
        l%=c;r%=c;
        if(l<=r)
            upd(l,r+1);
        else{
            upd(0,r+1);
            upd(l,c);
        }
    }
    cout<<seg[1]<<endl;



}

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