Submission #753473

#	Time	Username	Problem	Language	Result	Execution time	Memory
753473		karrigan	Strange Device (APIO19_strange_device)	C++14	100 / 100	1348 ms	172824 KiB

strange_device

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=1e6+9;
pll a[maxn];
vector<pll>b[maxn];
struct cus{
long long l,r;
bool operator < (const cus &p)const {
if (r==p.r)return l<p.l;
return r<p.r;
}
};
int bit[maxn*2];
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    int n;
    long long x,y;
    cin>>n>>x>>y;
    for1(i,1,n){
    cin>>a[i].fi>>a[i].se;
    }
    long long d1=a[n].se/y;
    long long t=x/gcd(x,y+1);
    if (d1<t){
        long long ans=0;
        for1(i,1,n){
        ans+=(a[i].se-a[i].fi+1);
        }
        cout<<ans;
        return 0;
    }
    long long z=t*y;
    for1(i,1,n){
    long long d=(a[i].fi)/z;
    a[i].fi-=z*d;
    a[i].se-=z*d;
    long long t1=a[i].fi/z,t2=a[i].se/z;
    if (t1+1<t2){
        b[i].pb({0,z-1});
        continue;
    }
    if (t1==t2){
        b[i].pb({a[i].fi%z,a[i].se%z});
        continue;
    }
    pll l1={a[i].fi,z-1};
    pll l2={0,a[i].se%z};
    b[i].pb(l1);
    b[i].pb(l2);
    }
    vector<long long>cord;
    for1(i,1,n){
    for (auto v:b[i]){
        cord.pb(v.fi);
        cord.pb(v.se+1);
    }
    }
    sort(all(cord));
    vector<long long>::iterator it=unique(all(cord));
    cord.resize(distance(cord.begin(),it));
    map<long long,int>newcord;
    for1(i,0,sz(cord)-1){
    newcord[cord[i]]=i;
    }
    for1(i,1,n){
    for (auto &v:b[i]){
        v.fi=newcord[v.fi];
        bit[v.fi]++;
        bit[newcord[v.se+1]]--;
    }
    }
    for1(i,1,sz(cord)-1){
    bit[i]+=bit[i-1];
    }
    long long ans=0;
    for1(i,0,sz(cord)-2){
    if (bit[i]){
        ans+=cord[i+1]-cord[i];
    }
    }
    for1(i,sz(cord)-1,sz(cord)-1){
    if (bit[i]){
        ans++;
    }
    }
    cout<<ans;
}

• 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