Submission #873484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873484	2023-11-15T07:10:31 Z	Danet	Strange Device (APIO19_strange_device)	C++14	100 / 100	1310 ms	100528 KB

strange_device

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")

#define tof_io  ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define double  long double
#define int     long long
#define pb      push_back

#define all(x)  x.begin(),x.end()
#define endl    '\n'
#define sz(x) 	x.size()
//const int mod = 998244353; //998244353 1e9+7 1e9+9
const int N = 5e3 + 23;	
const int lg = 23;
const int inf = 2e18;
int fac[N];
int inv[N];
//int  dnt_pow	(int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
//void dnt_bld	(){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
//int  dnt_ncr	(int r,int n){if(r>n) return 0; return fac[n] * inv[r] % mod * inv[n-r] % mod;}
void add (set<pair<int, int>>& st, int l, int r) 
{
	auto it = st.lower_bound({l, 0}), tmp = it;
	if (it != st.begin() && (--tmp)->second >= l) 
	{
		l = tmp->first;
		r = max(r, tmp->second);
		st.erase(tmp);
	}
	while (it != st.end()) 
	{
		if (r >= it->first) 
		{
			r = max(r, it->second);
			it = st.erase(it);
		} 
		else break;
	}
	st.insert({l, r});
}
 
int32_t main () 
{
	int n, a, b;
	cin >> n >> a >> b;
	int mod;
	if (a / __gcd(a, b+1) > inf / b) mod = inf;
	else mod = a / __gcd(a, b+1) * b;
	set<pair<int, int>> st;
	while (n--) 
	{
		int l, r;
		cin >> l >> r;
		if (r-l+1 >= mod) 
		{
			cout << mod << endl;
			return 0;
		}
		if (l % mod > r % mod) 
		{
			add(st, 0, r % mod);
			add(st, l % mod, mod-1);
		} else add(st, l % mod, r % mod);
	}
	int ans = 0;
	for (auto e: st) 
	{
		int l = e.first;
		int r = e.second;
		ans += r-l+1;
	}
	cout << ans ;
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	16 ms	860 KB	Output is correct
3	Correct	11 ms	832 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	360 KB	Output is correct
16	Correct	10 ms	856 KB	Output is correct
17	Correct	108 ms	6452 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	388 KB	Output is correct
4	Correct	344 KB	Output is correct
5	Correct	344 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	696 ms	408 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1151 ms	62928 KB	Output is correct
3	Correct	1134 ms	62892 KB	Output is correct
4	Correct	1249 ms	100368 KB	Output is correct

Subtask #5
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1151 ms	62928 KB	Output is correct
3	Correct	1134 ms	62892 KB	Output is correct
4	Correct	1249 ms	100368 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1162 ms	100188 KB	Output is correct
7	Correct	1182 ms	100528 KB	Output is correct
8	Correct	1168 ms	100144 KB	Output is correct
9	Correct	1247 ms	100372 KB	Output is correct

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	1151 ms	62928 KB	Output is correct
3	Correct	1134 ms	62892 KB	Output is correct
4	Correct	1249 ms	100368 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	105 ms	10280 KB	Output is correct
7	Correct	104 ms	10320 KB	Output is correct
8	Correct	106 ms	10320 KB	Output is correct
9	Correct	113 ms	10284 KB	Output is correct
10	Correct	106 ms	10320 KB	Output is correct
11	Correct	105 ms	10208 KB	Output is correct
12	Correct	107 ms	10380 KB	Output is correct
13	Correct	111 ms	10324 KB	Output is correct
14	Correct	107 ms	10324 KB	Output is correct
15	Correct	117 ms	10324 KB	Output is correct
16	Correct	114 ms	10312 KB	Output is correct
17	Correct	109 ms	10320 KB	Output is correct
18	Correct	1159 ms	99948 KB	Output is correct
19	Correct	1176 ms	100228 KB	Output is correct
20	Correct	1184 ms	100180 KB	Output is correct
21	Correct	112 ms	10324 KB	Output is correct
22	Correct	111 ms	10324 KB	Output is correct
23	Correct	323 ms	12964 KB	Output is correct

Subtask #7
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	115 ms	8484 KB	Output is correct
3	Correct	114 ms	8664 KB	Output is correct
4	Correct	1194 ms	100272 KB	Output is correct
5	Correct	114 ms	10324 KB	Output is correct
6	Correct	117 ms	10320 KB	Output is correct
7	Correct	119 ms	10324 KB	Output is correct
8	Correct	122 ms	10380 KB	Output is correct
9	Correct	112 ms	10356 KB	Output is correct
10	Correct	107 ms	10136 KB	Output is correct
11	Correct	108 ms	10252 KB	Output is correct
12	Correct	110 ms	10360 KB	Output is correct
13	Correct	113 ms	10328 KB	Output is correct
14	Correct	1202 ms	100252 KB	Output is correct
15	Correct	106 ms	9736 KB	Output is correct
16	Correct	1141 ms	100124 KB	Output is correct
17	Correct	1139 ms	100180 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct

Subtask #8
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	16 ms	860 KB	Output is correct
3	Correct	11 ms	832 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	360 KB	Output is correct
16	Correct	10 ms	856 KB	Output is correct
17	Correct	108 ms	6452 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	388 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	344 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	348 KB	Output is correct
27	Correct	1 ms	344 KB	Output is correct
28	Correct	696 ms	408 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	1151 ms	62928 KB	Output is correct
31	Correct	1134 ms	62892 KB	Output is correct
32	Correct	1249 ms	100368 KB	Output is correct
33	Correct	0 ms	348 KB	Output is correct
34	Correct	1162 ms	100188 KB	Output is correct
35	Correct	1182 ms	100528 KB	Output is correct
36	Correct	1168 ms	100144 KB	Output is correct
37	Correct	1247 ms	100372 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	105 ms	10280 KB	Output is correct
40	Correct	104 ms	10320 KB	Output is correct
41	Correct	106 ms	10320 KB	Output is correct
42	Correct	113 ms	10284 KB	Output is correct
43	Correct	106 ms	10320 KB	Output is correct
44	Correct	105 ms	10208 KB	Output is correct
45	Correct	107 ms	10380 KB	Output is correct
46	Correct	111 ms	10324 KB	Output is correct
47	Correct	107 ms	10324 KB	Output is correct
48	Correct	117 ms	10324 KB	Output is correct
49	Correct	114 ms	10312 KB	Output is correct
50	Correct	109 ms	10320 KB	Output is correct
51	Correct	1159 ms	99948 KB	Output is correct
52	Correct	1176 ms	100228 KB	Output is correct
53	Correct	1184 ms	100180 KB	Output is correct
54	Correct	112 ms	10324 KB	Output is correct
55	Correct	111 ms	10324 KB	Output is correct
56	Correct	323 ms	12964 KB	Output is correct
57	Correct	0 ms	344 KB	Output is correct
58	Correct	115 ms	8484 KB	Output is correct
59	Correct	114 ms	8664 KB	Output is correct
60	Correct	1194 ms	100272 KB	Output is correct
61	Correct	114 ms	10324 KB	Output is correct
62	Correct	117 ms	10320 KB	Output is correct
63	Correct	119 ms	10324 KB	Output is correct
64	Correct	122 ms	10380 KB	Output is correct
65	Correct	112 ms	10356 KB	Output is correct
66	Correct	107 ms	10136 KB	Output is correct
67	Correct	108 ms	10252 KB	Output is correct
68	Correct	110 ms	10360 KB	Output is correct
69	Correct	113 ms	10328 KB	Output is correct
70	Correct	1202 ms	100252 KB	Output is correct
71	Correct	106 ms	9736 KB	Output is correct
72	Correct	1141 ms	100124 KB	Output is correct
73	Correct	1139 ms	100180 KB	Output is correct
74	Correct	0 ms	344 KB	Output is correct
75	Correct	0 ms	348 KB	Output is correct
76	Correct	0 ms	348 KB	Output is correct
77	Correct	0 ms	348 KB	Output is correct
78	Correct	0 ms	348 KB	Output is correct
79	Correct	11 ms	1400 KB	Output is correct
80	Correct	1207 ms	100220 KB	Output is correct
81	Correct	1172 ms	100284 KB	Output is correct
82	Correct	1206 ms	100180 KB	Output is correct
83	Correct	1219 ms	100288 KB	Output is correct
84	Correct	1310 ms	100184 KB	Output is correct
85	Correct	1241 ms	100376 KB	Output is correct
86	Correct	335 ms	12880 KB	Output is correct
87	Correct	1 ms	348 KB	Output is correct

Submission #873484

Compilation message