제출 #1181957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181957		epicci23	이상한 기계 (APIO19_strange_device)	C++20	5 / 100	430 ms	39468 KiB

strange_device

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18 + 5;

void _(){
  int _n, _a, _b;
  cin >> _n >> _a >> _b;
  
  int n = _n, a = _a, b = _b;
  int rep;
  if( (a  / __gcd(a, b + 1)) >= (INF + b - 1) / b) rep = INF;
  else rep = (a  / __gcd(a, b + 1)) * b;

  vector<int> Zip, Add;

  Zip.push_back(0);
  Zip.push_back(rep - 1);
  Zip.push_back(rep);

  vector<array<int, 2>> V;
  bool ok = 0;


  for(int i = 1; i <= n; i++){
  	int _l, _r;
  	cin >> _l >> _r;
    int l = _l, r = _r;
  	int gl = l % rep;
  	int gr = r % rep;
  	int xl = l / rep;
  	int xr = r / rep;
  	if(xr - xl > 1) ok = 1;
  	else if(xl + 1 == xr && xl <= xr) ok = 1;
  	V.push_back({gl, gr});
    Zip.push_back(gl);
    Zip.push_back(gr + 1);
  }

  if(ok){
    cout << rep << '\n';
    return;
  }

  sort(all(Zip));
  Zip.erase(unique(all(Zip)), Zip.end());
  
  int m = sz(Zip);
  Add.assign(m, 0);

  for(array<int,2> X : V){
    int pl = lower_bound(all(Zip), X[0]) - Zip.begin();
    int pr = lower_bound(all(Zip), X[1] + 1) - Zip.begin();
    
    Add[pl]++;
    Add[pr]--;
    if(pl > pr) Add[0]++; 
  }

  int ans = 0, cur = 0;

  for(int i = 0; i + 1 < m; i++){
    cur += Add[i];
    if(i + 1 < m && cur > 0) ans += Zip[i + 1] - Zip[i];
  }

  cout << (long long) ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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