oj.uz

Submission #291990

# Submission time Handle Problem Language Result Execution time Memory
291990 2020-09-06T06:48:51 Z kajebiii Strange Device (APIO19_strange_device) C++17
10 / 100
 1077 ms 84620 KB 
// 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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 9 ms 1532 KB Output is correct
3 Correct 9 ms 1660 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 663 ms 72532 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 896 ms 84620 KB Output is correct
3 Incorrect 929 ms 84600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 896 ms 84620 KB Output is correct
3 Incorrect 929 ms 84600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 896 ms 84620 KB Output is correct
3 Incorrect 929 ms 84600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 101 ms 9236 KB Output is correct
3 Correct 101 ms 9316 KB Output is correct
4 Correct 1077 ms 84584 KB Output is correct
5 Correct 98 ms 9316 KB Output is correct
6 Correct 98 ms 9316 KB Output is correct
7 Correct 97 ms 9320 KB Output is correct
8 Correct 99 ms 9320 KB Output is correct
9 Correct 92 ms 9320 KB Output is correct
10 Correct 98 ms 9316 KB Output is correct
11 Correct 93 ms 9320 KB Output is correct
12 Correct 79 ms 9320 KB Output is correct
13 Correct 102 ms 9316 KB Output is correct
14 Correct 1059 ms 84592 KB Output is correct
15 Incorrect 102 ms 9316 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 9 ms 1532 KB Output is correct
3 Correct 9 ms 1660 KB Output is correct
4 Incorrect 0 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -