oj.uz

답안 #707441

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
707441 2023-03-09T02:50:21 Z josanneo22 이상한 기계 (APIO19_strange_device) C++17
0 / 100
 5000 ms 524288 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 40 ms 12640 KB Output is correct
3 Correct 63 ms 18200 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 8 ms 1220 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 41 ms 7040 KB Output is correct
16 Correct 25 ms 7016 KB Output is correct
17 Correct 58 ms 9664 KB Output is correct
18 Incorrect 1 ms 320 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 135 ms 32260 KB Output is correct
3 Correct 169 ms 32096 KB Output is correct
4 Correct 106 ms 30612 KB Output is correct
5 Execution timed out 5052 ms 62508 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 479 ms 62988 KB Output is correct
3 Runtime error 1663 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 479 ms 62988 KB Output is correct
3 Runtime error 1663 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 479 ms 62988 KB Output is correct
3 Runtime error 1663 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1341 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 40 ms 12640 KB Output is correct
3 Correct 63 ms 18200 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 8 ms 1220 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 316 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 41 ms 7040 KB Output is correct
16 Correct 25 ms 7016 KB Output is correct
17 Correct 58 ms 9664 KB Output is correct
18 Incorrect 1 ms 320 KB Output isn't correct
19 Halted 0 ms 0 KB -