제출 #708168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708168		veehj	Strange Device (APIO19_strange_device)	C++17	35 / 100	1787 ms	100216 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){if(!b)return a;else return gcd(b,a%b);}

int main() {
  ll n, a, b; cin >> n >> a >> b;
  a/=gcd(a, b+1);
  map<ll, ll> mp;
  while(n--){
    ll l, r; cin >> l >> r;
    if(r-l+1>=a*b){
      cout << a*b << endl;
      return 0;
    }
    l%=a*b;
    r%=a*b; 
    if(l>r){
      mp[l]++;
      mp[a*b]--;
      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