제출 #707441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707441		josanneo22	이상한 기계 (APIO19_strange_device)	C++17	0 / 100	5052 ms	524288 KiB

strange_device

#include<bits/stdc++.h>
#include<iostream>
#include<stdlib.h>
#include<cmath>
#include <algorithm>
#include<numeric>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<ll> vll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define trav(a,x) for (auto& a: x)
#define fr(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>=(b); i+=(s))
#define mp make_pair
#define pb push_back
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define in insert
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define out(x) cout<<x<<'\n'
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };

double pi = 3.141592;
void xd(string str)
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (str != "")
	{
		//freopen((str + ".in").c_str(), "r", stdin);
		//freopen((str + ".out").c_str(), "w", stdout);
	}
}
template <typename T>
T inverse(T a, T m) {
	T u = 0, v = 1;
	while (a != 0) {
		T t = m / a;
		m -= t * a; swap(a, m);
		u -= t * v; swap(u, v);
	}
	assert(m == 1);
	return u;
}

template <typename T>
class Modular {
public:
	using Type = typename decay<decltype(T::value)>::type;

	constexpr Modular() : value() {}
	template <typename U>
	Modular(const U& x) {
		value = normalize(x);
	}

	template <typename U>
	static Type normalize(const U& x) {
		Type v;
		if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
		else v = static_cast<Type>(x % mod());
		if (v < 0) v += mod();
		return v;
	}

	const Type& operator()() const { return value; }
	template <typename U>
	explicit operator U() const { return static_cast<U>(value); }
	constexpr static Type mod() { return T::value; }

	Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
	Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
	template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
	template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
	Modular& operator++() { return *this += 1; }
	Modular& operator--() { return *this -= 1; }
	Modular operator++(int) { Modular result(*this); *this += 1; return result; }
	Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
	Modular operator-() const { return Modular(-value); }

	template <typename U = T>
	typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
		value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
		return *this;
	}
	template <typename U = T>
	typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
		int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
		value = normalize(value * rhs.value - q * mod());
		return *this;
	}
	template <typename U = T>
	typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
		value = normalize(value * rhs.value);
		return *this;
	}

	Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

	template <typename U>
	friend const Modular<U>& abs(const Modular<U>& v) { return v; }

	template <typename U>
	friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

	template <typename U>
	friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

	template <typename U>
	friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

private:
	Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
	assert(b >= 0);
	Modular<T> x = a, res = 1;
	U p = b;
	while (p > 0) {
		if (p & 1) res *= x;
		x *= x;
		p >>= 1;
	}
	return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
	return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
	return to_string(number());
}

template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
	return stream << number();
}

template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
	typename common_type<typename Modular<T>::Type, int64_t>::type x;
	stream >> x;
	number.value = Modular<T>::normalize(x);
	return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = int(998244353);
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
	if (k < 0 || k > n) {
		return 0;
	}
	while ((int)fact.size() < n + 1) {
		fact.push_back(fact.back() * (int)fact.size());
		inv_fact.push_back(1 / fact.back());
	}
	return fact[n] * inv_fact[k] * inv_fact[n - k];
}

int add(int a, int b, int mod) { return (((a % mod) + (b % mod)) + mod) % mod; }
int sub(int a, int b, int mod) { return (((a % mod) - (b % mod)) + mod) % mod; }
int mul(int a, int b, int mod) { return (((a % mod) * (b % mod)) + mod) % mod; }
int bin(int a, int b, int mod) { int ans = 1; while (b) { if (b & 1) ans = mul(ans, a, mod); a = mul(a, a, mod); b >>= 1; }return ans; }
int inverse(int a, int mod) { return bin(a, mod - 2, mod); }
int divi(int a, int b, int mod) {
	return mul(a, inverse(b, mod), mod);
}
ll add(ll a, ll b, ll mod) { return (((a % mod) + (b % mod)) + mod) % mod; }
ll sub(ll a, ll b, ll mod) { return (((a % mod) - (b % mod)) + mod) % mod; }
ll mul(ll a, ll b, ll mod) { return (((a % mod) * (b % mod)) + mod) % mod; }
ll bin(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) ans = mul(ans, a, mod); a = mul(a, a, mod); b >>= 1; }return ans; }
ll inverse(ll a, ll mod) { return bin(a, mod - 2, mod); }
ll divi(ll a, ll b, ll mod) {
	return mul(a, inverse(b, mod), mod);
}
ll ex(int base, int power, int modulo)
{
	if (power == 0)
		return 1;
	ll result = ex(base, power / 2, modulo);
	if (power % 2 == 1)
		return(((result * result) % modulo) * base) % modulo;
	else return (result * result) % modulo;
}
ll exp(int base, int power)
{
	if (power == 0)
		return 1;
	ll result = exp(base, power / 2);
	if (power % 2 == 1)
		return(result * result) * base;
	else return (result * result);
}
int gcd(int a, int b) {
	if (b == 0)return a;
	else return gcd(b, a % b);
}
int lcm(int a, int b) {
	return a * b / gcd(a, b);
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
ll fac(int x, ll mod) {
	ll factorial = 1;
	for (ll i = 1; i <= x; ++i) {
		factorial = mul(factorial, i, mod);
	}
	return factorial % mod;
}
ll npr(int x, int c, ll mod) {
	if (x < c) return 0;
	if (x == c) return fac(x, mod);
	else return divi(fac(x, mod), (fac(x - c, mod)), mod);
}
ll ncr(int x, int c, ll mod) {
	if (x < c) return 0;
	if (x == c) return 1;
	else return divi(fac(x, mod), mul((fac(x - c, mod)), fac(c, mod), mod), mod);
}
void bton(string s) { stoll(s, nullptr, 2); }
bool isPrime(int n)
{
	if (n == 2 || n == 3)
		return true;

	if (n <= 1 || n % 2 == 0 || n % 3 == 0)
		return false;
	for (int i = 5; i * i <= n; i += 6) {
		if (n % i == 0 || n % (i + 2) == 0)
			return false;
	}

	return true;
}
int ceil_int(int first_number, int divider) {
	if (first_number % divider == 0) return first_number / divider;
	else return first_number / divider + 1;
}
ll ceil_ll(ll first_number, ll divider) {
	if (first_number % divider == 0) return first_number / divider;
	else return first_number / divider + 1LL;
}
ll chinese(vll num, vll rem) {
	vll pp; pp.clear();
	ll prod = 1LL;
	FOR(i, 0, sz(num))prod *= num[i];
	FOR(i, 0, sz(num))pp.push_back(prod / num[i]);
	vll inv; inv.clear();
	FOR(i, 0, sz(pp)) {
		inv.push_back(ex(pp[i], num[i] - 2, num[i]));
	}
	ll ans = 0LL;
	FOR(i, 0, sz(pp)) {
		ans = ans % prod + (((rem[i] * pp[i]) % prod) * (inv[i] % prod)) % prod;
		ans %= prod;
	}
	return ans;
}
//ncr(n+k-1,k-1) where a[i]>=0 need to consider the condition where a[i] is positive int or odd or whatever(on this n will change)
vector<int> smallest_factor;
vector<bool> prime;
vector<int> primes;
// Note: this sieve is O(n), but the constant factor is worse than the O(n log log n) sieve due to the multiplication.
void sieve(int maximum) {
	maximum = max(maximum, 1);
	smallest_factor.assign(maximum + 1, 0);
	prime.assign(maximum + 1, true);
	prime[0] = prime[1] = false;
	primes = {};

	for (int i = 2; i <= maximum; i++) {
		if (prime[i]) {
			smallest_factor[i] = i;
			primes.push_back(i);
		}

		for (int p : primes) {
			if (p > smallest_factor[i] || int64_t(i) * p > maximum)
				break;
			prime[i * p] = false;
			smallest_factor[i * p] = p;
		}
	}
}
long long query_ask(int a, int b) {
	cout << "? " << a << ' ' << b << endl;
	long long x; cin >> x;
	return x;
}
void query_ans(long long a) {
	cout << "! " << a << endl;
	return;
}
int computeXOR(int n)// from 0 to n-1
{
	if (n % 4 == 0)
		return n;
	if (n % 4 == 1)
		return 1;
	if (n % 4 == 2)
		return n + 1;
	return 0;
}
int digit_sum(int g) {
	int cnt = 0;
	while (g > 0) {
		cnt += g % 10;
		g /= 10;
	}
	return cnt;
}
ll inf = 1e18 + 1;
void solve()
{
	ll n, a, b; cin >> n >> a >> b;
	if (n == 1) {
		ll m;
		if ((ll)a * (ll)b > (ll)inf)
			m = inf;
		else
			m = a * b;
		ll x, y;
		cin >> x >> y;
		cout << min(y - x + 1, m);
	}
	else {
		set<pair<ll, ll>> p;
		for (int i = 0; i < n; i++) {
			ll x, y; cin >> x >> y;
			for (ll j = x; j <= y; j++) {
				p.insert(make_pair((j + ceil_ll(j, b)) % a, j % b));
			}
		}
		cout << p.size() << '\n';
	}
}
int main()
{
	xd("");
	int t = 1; //cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

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