Submission #982445

#	Time	Username	Problem	Language	Result	Execution time	Memory
982445		vjudge1	Strange Device (APIO19_strange_device)	C++17	40 / 100	4910 ms	175636 KiB

strange_device

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
using namespace std;
vll val,vval;int sz;
vector<pll>t;
vector<ll>lz;
void build(int i,int l,int r){
    if(l==r)return void(t[i]={0,vval[l]-vval[l-1]});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]={0,t[2*i].s+t[2*i+1].s};
}
void push(int i,int l,int r){
    t[i].f+=lz[i];
    if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
    lz[i]=0;
}
void upd(int i,int l,int r,int tl,int tr,ll v){
    push(i,l,r);
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        lz[i]+=v;push(i,l,r);return;
    }int m=(l+r)>>1;upd(2*i,l,m,tl,tr,v);upd(2*i+1,m+1,r,tl,tr,v);
    if(t[2*i].f==t[2*i+1].f)t[i]={t[2*i].f,t[2*i].s+t[2*i+1].s};
    else t[i]=min(t[2*i],t[2*i+1]);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    ll n,a,b,d;cin>>n>>a>>b;d=a/__gcd(a,b+1);val.pb(0);val.pb(d);
    ll ans=0;vector<pair<ll,pll>>v;
    for(int i=0;i<n;i++){
        ll l,r;cin>>l>>r;
        ll x=l/b,y=r/b,z=l%b,tt=r%b;
        if(z<=tt){
            if(0<=z-1&&x+1<=y)v.pb({0,{x+1,y}}),v.pb({z,{-x-1,-y}}),val.pb((x+1)%d),val.pb((y)%d+1);
            if(z<=tt&&x<=y)v.pb({z,{x,y}}),v.pb({tt+1,{-x,-y}}),val.pb(x%d),val.pb((y)%d+1);
            if(tt+1<=b-1&&x<=y-1)v.pb({tt+1,{x,y-1}}),v.pb({b,{-x,-y+1}}),val.pb(x%d),val.pb((y-1+d)%d+1);
        }
        else {
            if(0<=tt&&x+1<=y)v.pb({0,{x+1,y}}),v.pb({tt+1,{-x-1,-y}}),val.pb((x+1)%d),val.pb((y)%d+1);
            if(tt+1<=z-1&&x+1<=y-1)v.pb({tt+1,{x+1,y-1}}),v.pb({z,{-x-1,-y+1}}),val.pb((x+1)%d),val.pb((y-1+d)%d+1);
            if(z<=b-1&&x<=y-1)v.pb({z,{x,y-1}}),v.pb({b,{-x,-y+1}}),val.pb(x%d),val.pb((y-1+d)%d+1);
        }
    }sort(v.begin(),v.end());sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());vval=val;vval.pb(d);
    sz=(int)val.size();t.resize(4*((int)val.size()+1)),lz.resize(4*((int)val.size()+1),0);build(1,1,sz);
    if(val.size()>=1000000)return 0;
    for(int i=0;i<v.size()-1;i++){
        ll x=abs(v[i].s.f)/d,y=abs(v[i].s.s)/d,z=abs(v[i].s.f)%d,tt=abs(v[i].s.s)%d;
        ll add=y-x+1;
        if(v[i].s.f>=0&&v[i].s.s>=0){
            if(z<=tt){
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,add);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
            }
            else {
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,add-2);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,add-1);
            }
        }
        else {
            if(z<=tt){
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,-add);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
            }
            else {
                int tl,tr;
                tl = upper_bound(val.begin(),val.end(),0)-val.begin();
                tr = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
                tl = upper_bound(val.begin(),val.end(),tt+1)-val.begin();
                tr = upper_bound(val.begin(),val.end(),z)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+2);
                tl = upper_bound(val.begin(),val.end(),z)-val.begin();
                tr = upper_bound(val.begin(),val.end(),d)-val.begin();
                upd(1,1,sz,tl,tr-1,-add+1);
            }
        }
        if(t[1].f==0)ans+=(v[i+1].f-v[i].f)*(d-t[1].s);
    }cout<<ans;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<v.size()-1;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: 20 / 20
• Subtask 8: 0 / 30