제출 #568694

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

strange_device

// You can't change other people; you can only change yourself.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;

// Data types
using i8	= __int128;
using ll	= long long;
using si	= short int;
using ld	= long double;

// Pairs
using pi8	= pair<i8, i8>;
using pll	= pair<ll, ll>;
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pld	= pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename T>
using ordered_set	= tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

// Constants
const ll ModA	= 998244353;
const ll ModC	= 1e9 + 7;
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

i8 gcd(i8 x, i8 y) {
	if (!y) return x;
	return gcd(y, x % y);
}

ll n, A, B;
vector<pi8> segments;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	scanf("%lld %lld %lld", &n, &A, &B);
	i8 _A = A, _B = B;

	i8 _loop = ((i8)1 * _A * _B) / gcd(_A, _B+1);
	ll loop;
	if (_loop >= INF) {
		loop = INF;
	} else {
		loop = _loop;
	}

	for (ll l, r, i = 1; i <= n; i++) {
		scanf("%lld %lld", &l, &r);

		if (r - l + 1 >= loop) {
			printf("%lld\n", loop);
			return 0;
		} else {
			ll lx = l % loop, rx = r % loop;
			if (lx <= rx) {
				segments.push_back({lx, 1});
				segments.push_back({rx+1, -1});
			} else {
				segments.push_back({0, 1});
				segments.push_back({rx+1, -1});

				segments.push_back({lx, 1});
				segments.push_back({loop, -1});
			}
		}
	}

	sort(segments.begin(), segments.end());
	ll ans = 0, depth = 0, lastOpen = -1;
	for (auto &[pos, d] : segments) {
		if (depth == 0) {
			lastOpen = pos;
		}
		depth += d;
		if (depth == 0) {
			ans += pos - lastOpen;
		}
	}
	printf("%lld\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

strange_device.cpp: In function 'int main()':
strange_device.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%lld %lld %lld", &n, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
strange_device.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%lld %lld", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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