Submission #708177

#	Time	Username	Problem	Language	Result	Execution time	Memory
708177		veehj	Strange Device (APIO19_strange_device)	C++17	35 / 100	1743 ms	69088 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
ll gcd(ll a, ll b){ return b ? gcd(b,a%b) : a; }

int main() {
  ll n, a, b; cin >> n >> a >> b;
  a/=gcd(a, b+1);
  __int128_t ml = a*b;
  map<ll, ll> mp;
  while(n--){
    ll l, r; cin >> l >> r;
    if(r-l+1>=ml){
      cout << (ll)ml << endl;
      return 0;
    }
    l%=ml;
    r%=ml; 
    if(l>r){
      mp[l]++;
      mp[ml]--;
      mp[0]++;
      mp[r+1]--;
    }
    else{
      mp[l]++;
      mp[r+1]--;
    }
  }
  // 1 0 1 -1 -1 0 1 0 -1
  // 1 1 2  1  0 0 1 1  0
  ll cnt=0, nw=0, ans=0, pcnt=0;
  for(auto& u : mp){
    cnt+=u.S;
    // cout << "[" << u.first << ',' << u.second << ']' << cnt << endl;
    if(!pcnt) nw=u.F;
    if(!cnt) ans+=u.F-nw;
    pcnt=cnt;
  }
  cout << ans;
} 

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