제출 #1182057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182057		SalihSahin	Strange Device (APIO19_strange_device)	C++20	100 / 100	676 ms	94856 KiB

strange_device

#include "bits/stdc++.h"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18;
const int N = 1e6;

int32_t main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0), cout.tie(0);
   int n, a, b;
   cin>>n>>a>>b;
   vector<int> l(n), r(n);
   for(int i = 0; i < n; i++){
      cin>>l[i]>>r[i];
   }

   bool big = 0;
   int gc = __gcd(a, b+1);

   big = (a / gc > inf / b);
   if(big){
      int tot = 0;
      for(int i = 0; i < n; i++){
         int len = r[i] - l[i] + 1;
         tot += len;
      }
      cout<<tot<<endl;
      return 0;
   }

   int per = (a / gc) * b;

   bool all = 0;
   vector<pair<int, int> > upd;
   set<int> ste;
   int add0 = 0;

   for(int i = 0; i < n; i++){
      int df = (r[i] / per) - (l[i] / per);
      int lmod = l[i] % per;
      int rmod = r[i] % per;
      ste.insert(lmod);
      ste.insert(rmod+1);

      if(r[i] - l[i] + 1 >= per) all = 1;
      else if(df == 1){
         add0++;
      }
      upd.pb({lmod, rmod+1});
   }
   ste.insert(0);
   ste.insert(per - 1);
   ste.insert(per);

   vector<int> vec;
   for(auto itr: ste){
      vec.pb(itr);
   }
   vector<int> add(ste.size());
   add[0] += add0;

   for(auto itr: upd){
      auto l = lower_bound(vec.begin(), vec.end(), itr.first) - vec.begin();
      auto r = lower_bound(vec.begin(), vec.end(), itr.second) - vec.begin();
      add[l]++;
      add[r]--;
   }

   if(all){
      cout<<per<<endl;
   }
   else{
      int ans = 0, now = 0;
      for(int i = 0; i < vec.size()-1; i++){
         now += add[i];
         if(now > 0){
            ans += vec[i+1] - vec[i];
         }
      }
      cout<<ans<<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