Submission #567736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
567736	2022-05-24T06:10:40 Z	8e7	Strange Device (APIO19_strange_device)	C++17	65 / 100	655 ms	61404 KB

strange_device

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T,class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
ll inf = 1LL<<60;
ll mul(ll a, ll b) {
	ll ret = 0;
	while (b) {
		if (a > inf) return inf;
		if (b & 1) ret += a;
		a += a;
		b >>= 1;
		if (ret > inf) return inf;
	}
	return ret;
}
int main() {
	io
	ll n, A, B;
	cin >> n >> A >> B;
	ll cy = mul(A / __gcd(A, B + 1), B);
	vector<pii> ev;
	for (int i = 0;i < n;i++) {
		ll l, r;
		cin >> l >> r;
		l %= cy, r %= cy;
		if (l <= r) {
			ev.push_back({l, 1});
			ev.push_back({r + 1, -1});
		} else {
			ev.push_back({l, 1});
			ev.push_back({0, 1});
			ev.push_back({r+1, -1});
		}
	}
	ev.push_back({cy, 0});
	sort(ev.begin(), ev.end());
	
	ll prv = -1, val = 0, ans = 0;
	int siz = ev.size();
	for (int i = 0;i < siz;i++) {
		int tmp = i;
		ll to = val;	
		while (tmp < siz - 1 && ev[tmp+1].ff == ev[i].ff) {
			to += ev[tmp].ss;
			tmp++;
		}
		to += ev[tmp].ss;
		if (val) ans += ev[i].ff - prv;
		val = to;
		prv = ev[i].ff;
		i = tmp;
	}
	cout << ans << "\n";	
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	8 ms	1248 KB	Output is correct
3	Correct	6 ms	1240 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 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	0 ms	312 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	6 ms	1292 KB	Output is correct
17	Correct	60 ms	7288 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	2 ms	372 KB	Output is correct
5	Correct	360 ms	56844 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	559 ms	38648 KB	Output is correct
3	Correct	553 ms	49704 KB	Output is correct
4	Correct	503 ms	61188 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	559 ms	38648 KB	Output is correct
3	Correct	553 ms	49704 KB	Output is correct
4	Correct	503 ms	61188 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	550 ms	61324 KB	Output is correct
7	Correct	510 ms	61228 KB	Output is correct
8	Correct	557 ms	61276 KB	Output is correct
9	Correct	631 ms	61404 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	559 ms	38648 KB	Output is correct
3	Correct	553 ms	49704 KB	Output is correct
4	Correct	503 ms	61188 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	50 ms	7188 KB	Output is correct
7	Correct	54 ms	7212 KB	Output is correct
8	Correct	48 ms	7252 KB	Output is correct
9	Correct	53 ms	7180 KB	Output is correct
10	Correct	48 ms	7188 KB	Output is correct
11	Correct	56 ms	7356 KB	Output is correct
12	Correct	64 ms	7236 KB	Output is correct
13	Correct	56 ms	7228 KB	Output is correct
14	Correct	47 ms	7216 KB	Output is correct
15	Correct	57 ms	7280 KB	Output is correct
16	Correct	59 ms	7216 KB	Output is correct
17	Correct	47 ms	7208 KB	Output is correct
18	Correct	553 ms	52188 KB	Output is correct
19	Correct	520 ms	61144 KB	Output is correct
20	Correct	647 ms	61100 KB	Output is correct
21	Correct	62 ms	7192 KB	Output is correct
22	Correct	47 ms	7288 KB	Output is correct
23	Correct	154 ms	26720 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	70 ms	7240 KB	Output is correct
3	Correct	54 ms	7224 KB	Output is correct
4	Correct	655 ms	50664 KB	Output is correct
5	Correct	60 ms	7380 KB	Output is correct
6	Correct	54 ms	7228 KB	Output is correct
7	Correct	61 ms	7216 KB	Output is correct
8	Correct	60 ms	7204 KB	Output is correct
9	Correct	52 ms	7228 KB	Output is correct
10	Correct	61 ms	7320 KB	Output is correct
11	Correct	54 ms	7228 KB	Output is correct
12	Correct	63 ms	7236 KB	Output is correct
13	Correct	58 ms	7228 KB	Output is correct
14	Correct	652 ms	61220 KB	Output is correct
15	Correct	56 ms	7200 KB	Output is correct
16	Correct	524 ms	61368 KB	Output is correct
17	Correct	519 ms	61404 KB	Output is correct
18	Correct	1 ms	320 KB	Output is correct

Subtask #8
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	8 ms	1248 KB	Output is correct
3	Correct	6 ms	1240 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 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	0 ms	312 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	6 ms	1292 KB	Output is correct
17	Correct	60 ms	7288 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Incorrect	0 ms	212 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Submission #567736

Compilation message