제출 #1181919

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

strange_device

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

const int inf = 2e18 + 5000;
const int mod = 998244353;
const int N = 2e6 + 5;

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];
      l[i]--, r[i]--;
   }

   int ninf = inf / gcd(a, b+1) / b;
   if(a > ninf){
      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 / gcd(a, b+1) * b;

   bool all = 0;
   map<int, int> upd;
   set<int> ste;

   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);
      if(rmod != a*b-1) ste.insert(rmod+1);

      if((r[i] - l[i] + 1) >= per) all = 1;
      else if(df == 1){
         upd[lmod]++;
         upd[0]++;
         if(rmod != a*b-1) upd[rmod+1]--;
      }
      else{
         upd[lmod]++;
         if(rmod != a*b-1) upd[rmod+1]--;
      }
   }
   ste.insert(0);
   ste.insert(per-1);

   if(all){
      cout<<a*b<<endl;
   }
   else{
      int ans = 0, delt = 0, lst = 0;
      for(auto itr: ste){
         if(delt > 0){
            ans += (itr - lst);
         }
         delt += upd[itr];
         lst = itr;
      }
      if(delt > 0) ans++;
      cout<<ans<<endl;
   }
   return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 20
• Subtask 7: 20 / 20
• Subtask 8: 0 / 30