Submission #291990

#	Time	Username	Problem	Language	Result	Execution time	Memory
291990		kajebiii	Strange Device (APIO19_strange_device)	C++17	10 / 100	1077 ms	84620 KiB

strange_device

// Comment
//

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

using pli = pair<ll, ll>;
using ti = tuple<ll, ll, int>;

ll gcd(ll a, ll b) {
	if(b == 0) return 1;
	return gcd(b, a%b);
}

int N; ll A, B, G;
vector<ti> Lines;

struct PT {
	ll x, y; // 0 <= x <= A/G, 0 <= y < B
	PT(ll _x, ll _y): x(_x), y(_y) {}
	PT up() {
		ll _x = x, _y = y;
		_y++;
		if(y == B) {
			_x++;
			_y = 0;
		}
		return PT(_x, _y);
	}
};


vector<ll> getNums(ll t) {
	// t = (xA + n (A/G) + m) B + z;
	
	ll a = t / B, z = t % B;
	ll x = a / A, y = a % A;
	ll n = y / (A/G), m = y % (A/G);
	ll nums[4] = {x, n, m, z};
	return vector<ll>(nums, nums+4);
}

int main() {
	cin >> N >> A >> B;
	G = gcd(A, B+1);

	for(int i=1; i<=N; i++) {
		ll x, y; scanf("%lld%lld", &x, &y);
		vector<ll> xs = getNums(x);
		vector<ll> ys = getNums(y);

		ll xabg = xs[0]*G + xs[1];
		ll yabg = ys[0]*G + ys[1];

		if(xabg+2 <= yabg) {
			printf("%lld\n", (A/G) * B);
			return 0;
		}
		
		Lines.emplace_back(xs[2], xs[3], +1);
		PT pt = PT(ys[2], ys[3]).up();
		Lines.emplace_back(pt.x, pt.y, -1);

		if(xabg != yabg) {
			Lines.emplace_back(0, 0, +1);
			Lines.emplace_back(A/G, 0, -1);
		}
	}

	Lines.emplace_back(A/G, 0, 0);
	sort(ALL(Lines));
	ll ans = 0; int now = 0;
	for(int i=0; i+1<SZ(Lines); i++) {
		ll x, y; int v; tie(x, y, v) = Lines[i];
		ll nx, ny; int nv; tie(nx, ny, nv) = Lines[i+1];

		now += v;
		if(now >= 1) {
			ans += (nx - x) * B + (ny - y);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   ll x, y; scanf("%lld%lld", &x, &y);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~

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