Submission #541857

#	Time	Username	Problem	Language	Result	Execution time	Memory
541857		NicolaAbusaad2014	Strange Device (APIO19_strange_device)	C++14	20 / 100	1315 ms	524288 KiB

strange_device

/**
 * Prof.Nicola
**/
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
#define bitl __builtin_clz
#define bitr __builtin_ctz
#define bits __builtin_popcount
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
long long log(long long x,long long z){if(x<z){return 0;}return 1+log(x/z,z);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
struct segment_tree
{
    struct node
    {
        long long value=0,upd=0,left=0,right=0,a=0,b=0;
        bool extended=false;
    };
    node dum;
    vector<node>tree;
    node operation(node x,node z)
    {
        node ret;
        ret.value=x.value+z.value;
        ret.left=min(x.left,z.left);
        ret.right=max(x.right,z.right);
        return ret;
    }
    void extend(long node)
    {
        if(tree[node].left==tree[node].right||tree[node].extended){
            return;
        }
        tree[node].extended=true;
        tree[node].a=tree.size();
        tree.push_back(dum);
        tree.back().left=tree[node].left;
        tree.back().right=(tree[node].left+tree[node].right)/2;
        tree[node].b=tree.size();
        tree.push_back(dum);
        tree.back().left=(tree[node].left+tree[node].right+1)/2;
        tree.back().right=tree[node].right;
    }
    void push(long node)
    {
        extend(node);
        if(tree[node].upd){
            tree[node].value=tree[node].right-tree[node].left+1;
            if(tree[node].left!=tree[node].right){
                tree[tree[node].a].upd=1;
                tree[tree[node].b].upd=1;
            }
            tree[node].upd=0;
        }
    }
    void build()
    {
        tree.clear();
        dum.value=0;
        dum.upd=0;
        dum.left=2e18;
        dum.right=-2e18;
        tree.push_back(dum);
        tree[0].left=0;
        tree[0].right=(1ll<<60)-1;
    }
    node get(long long l,long long r,long node=0)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return dum;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            return tree[node];
        }
        return operation(get(l,r,tree[node].a),get(l,r,tree[node].b));
    }
    void update(long long l,long long r,long node=0)
    {
        push(node);
        if(tree[node].left>r||tree[node].right<l){
            return;
        }
        if(tree[node].left>=l&&tree[node].right<=r){
            tree[node].upd=1;
            push(node);
            return;
        }
        update(l,r,tree[node].a);
        update(l,r,tree[node].b);
        tree[node].value=tree[tree[node].a].value+tree[tree[node].b].value;
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,A,B,s,sum=0,l,r;
    cin>>n>>A>>B;
    vector<pair<long long,long long> >v(n);
    re(v);
    REP(i,0,n){
        sum+=v[i].S-v[i].F+1;
    }
    if(log(A)+log(B)-log(__gcd(A,B+1))>log(1e18)){
        cout<<sum<<endl;
        return 0;
    }
    s=B*(A/__gcd(A,B+1));
    segment_tree st;
    st.build();
    REP(i,0,n){
        if(v[i].S-v[i].F+1>=s){
            cout<<s<<endl;
            return 0;
        }
        l=v[i].F%s;
        r=v[i].S%s;
        if(l<=r){
            st.update(l,r);
            continue;
        }
        st.update(0,r);
        st.update(l,s-1);
    }
    cout<<st.get(0,s-1).value<<endl;
    return 0;
}

Compilation message (stderr)

strange_device.cpp: In instantiation of 'void re(std::vector<_Tp>&) [with T = std::pair<long long int, long long int>]':
strange_device.cpp:137:9:   required from here
strange_device.cpp:26:53: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
      |                                                    ~^~~~~~~~~

• 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