Submission #1182049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182049		SalihSahin	Strange Device (APIO19_strange_device)	C++20	45 / 100	1444 ms	188380 KiB

strange_device

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

const int inf = 3e18;
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];
      l[i]--, r[i]--;
   }

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

   big |= (a > inf / gc / b);
   big |= (b > inf / gc / a);
   big |= (gc > inf / a / 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;
   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);
      ste.insert(rmod+1);

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

   if(all){
      cout<<per<<endl;
   }
   else{
      int lst = 0;
      map<int, int> nxt;
      for(auto itr: ste){
         nxt[lst] = itr;
         lst = itr;
      }

      int ans = 0, delt = 0;
      for(auto itr: ste){
         if(itr == per) continue;
         delt += upd[itr];
         if(delt > 0){
            ans += (nxt[itr] - itr);
         }
      }
      cout<<ans<<endl;
   }
   
   return 0;
}

• Subtask 1: 10 / 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