제출 #1044686

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1044686		vjudge1	이상한 기계 (APIO19_strange_device)	C++17	100 / 100	446 ms	98580 KiB

strange_device

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
const ll mod = 1e9 + 7;
const ll N = 2e5 + 37;
template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p);
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s);
template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s);
const ll inf = (ll)2e18 + 37;
ll get_period(ll a, ll b) {
  ll ans = a / gcd(a, b + 1);
  if(inf / ans < b) {
    return -1;
  }
  return ans * b;
}


void solve_inf_case(ll n) {
  ll ans = 0;
  for(ll i = 0; i < n; ++i) {
    ll l, r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  cout << ans << endl;
}

void solve() {
  ll n, A, B;
  cin >> n >> A >> B;
  ll period = get_period(A, B);
  if(period == -1) {
    solve_inf_case(n);
    return;
  }
  set<pair<ll, ll> > s; // {r, l}

  auto insert_p = [&](pair<ll, ll> p) -> void
  {
    assert(p.first >= p.second);
    // cout << "Hey : " << p.second << ' ' << p.first << endl;
    while(!s.empty() and p.second <= s.rbegin()->first) {
      auto it = s.end();
      --it;
      p = {max(p.first, it->first), min(p.second, it->second)};
      s.erase(it);
    }
    s.insert(p);
  };
  vector<pair<ll, ll> > a;
  for(ll i = 0; i < n; ++i) {
    pair<ll, ll> p; // {r, l}
    cin >> p.second >> p.first;
    bool twice = false;
    if(p.first - p.second >= period - (p.second % period)) {
      twice = true;
    }
    p.second %= period;
    p.first %= period;
    // cout << "Hi : " << p.second << ' ' << p.first << endl;
    if(twice) {
      a.push_back({period - 1, p.second});
      a.push_back({p.first, 0});
    }
    else {
      a.push_back(p);
    }
  }
  sort(a.begin(), a.end());
  for(const auto& p : a)
    insert_p(p);
  // cout << period << endl;
  ll ans = 0;
  for(auto p : s){
    // cout << p.second << " " << p.first << endl;
    ans += p.first - p.second + 1;
  }
  cout << ans << endl;
}


signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // signed t; cin >> t; while(t--) 
    solve();
}

template<typename T, size_t N>
std::ostream& operator<<(std::ostream& os, const std::array<T, N>& a) {
  os << "[";
  for(size_t i = 0; i + 1 < N; ++i) {
    os << a[i] << ", ";
  }
  if(N > 0)
    os << a[N - 1];
  os << "]";
  return os;
}
 
template<typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ") ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << '[';
  for(auto x : v)
    os << x << ", ";
  os << "] ";
  return os;
}
 
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

template<typename T, typename cmp>
std::ostream& operator<<(std::ostream& os, const std::set<T, cmp>& s) {
  os << "{";
  for(auto x : s)
    os << x << ", ";
  os << "} ";
  return os;
}

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