Submission #260698

#	Time	Username	Problem	Language	Result	Execution time	Memory
260698		tko919	Strange Device (APIO19_strange_device)	C++17	100 / 100	3034 ms	155364 KiB

strange_device

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
//end

typedef pair<ll,ll> P;

int main(){
   ll n,a,b; cin>>n>>a>>b;
   ll g=a/gcd(a,b+1);
   if(b>INF/g)g=INF; else g*=b;
   vector<P> rng; vector<ll> vs={0,g};
   rep(i,0,n){
      ll lb,rb; cin>>lb>>rb; rb++;
      if(rb-lb>g){
         cout<<g<<endl;
         return 0;
      }
      lb%=g; rb%=g;
      vs.push_back(lb);
      vs.push_back(rb);
      if(lb<rb){
         rng.push_back({lb,1});
         rng.push_back({rb,-1});
      }
      else{
         rng.push_back({0,1});
         rng.push_back({rb,-1});
         rng.push_back({lb,1});
         rng.push_back({g,-1});
      }
   }
   sort(ALL(vs)); vs.erase(unique(ALL(vs)),vs.end());
   map<ll,int> rev;
   rep(i,0,vs.size())rev[vs[i]]=i;
   int m=vs.size();
   vector<ll> rui(m+10,0);
   rep(i,0,rng.size())rui[rev[rng[i].first]]+=rng[i].second;
   rep(i,0,m)rui[i+1]+=rui[i];
   ll res=0;
   rep(i,0,m){
      if(rui[i])res+=vs[i+1]-vs[i];
   }
   cout<<res<<endl;
   return 0;
}

• 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