oj.uz

Submission #733173

# Submission time Handle Problem Language Result Execution time Memory
733173 2023-04-30T07:53:23 Z minhcool Strange Device (APIO19_strange_device) C++17
100 / 100
 1684 ms 318684 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e6 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

/*
What I'm trying to do:
Just imagine that we want all intervals that begins with (sth, 0) to ((sth + B - 1) % A, B - 1), the rest
has like O(n) segments. Inside this interval, there will be no changes made to t/B
Ez as hell
*/

int n, a, b;

//vector<int> inters[N];
vector<ii> full;
unordered_map<int, int> mp;
bool ok[N];
vector<ii> part[N];

int cnt;

void process(){
	cin >> n >> a >> b;
	int temp = __gcd(a, b + 1);
	for(int i = 1; i <= n; i++){
		int x, y;
		cin >> x >> y;
		int temp1 = x / b + 1, temp2 = y / b - 1;
		if(temp1 <= temp2){
			if((temp2 - temp1 + 1) >= a/temp){
				cout << a * b / temp;
				exit(0);
			}
			temp1 %= a/temp, temp2 %= a/temp;
			if(temp1 <= temp2) full.pb({temp1, temp2});
			else{
				full.pb({temp1, a/temp - 1});
				full.pb({0, temp2});
			}
		}
		if((x/b) == (y/b)){
			if(mp.find((x/b) % (a/temp)) == mp.end()){
				cnt++;
				mp[(x/b) % (a/temp)] = cnt;
			}
		//	cout << x << " " << y << " " << cnt << " " << x%b << " " << y%b << "\n";
			part[mp[(x/b) % (a/temp)]].pb({x % b, y % b});	
		}
		else{
			//temp1 = , temp2 = (y / b) * b;
			if(mp.find((x/b) % (a/temp)) == mp.end()){
				cnt++;
				mp[(x/b) % (a/temp)] = cnt;
			}
			part[mp[(x/b) % (a/temp)]].pb({x % b, b - 1});
			//cout << x << " " << y << " " << cnt << " " << x%b << " " << b-1 << "\n";
			if(mp.find((y/b) % (a/temp)) == mp.end()){
				cnt++;
				mp[(y/b) % (a/temp)] = cnt;
			}
			part[mp[(y/b) % (a/temp)]].pb({0, y % b});
		//	cout << x << " " << y << " " << cnt << " " << 0 << " " << y%b << "\n";
		}
	}
	//sort(full.begin(), full.end());
	vector<ii> updates;
	for(auto it : full){
		updates.pb({it.fi, 1});
		updates.pb({it.se + 1, -1});
	}
	for(auto it : mp) updates.pb({it.fi, oo});
	sort(updates.begin(), updates.end());
	int lst = -oo, sum = 0, ans = 0;
	for(auto it : updates){
		if(lst != -oo) ans += b * (it.fi - lst) * (sum != 0);
		lst = it.fi;
		if(abs(it.se) == 1) sum += it.se;
		if(it.se == oo) ok[mp[it.fi]] = (sum == 0);
	}
//	cout << ans << "\n";
//	for(auto it : mp) cout << it.fi << " " << it.se << "\n";
	for(int i = 1; i <= cnt; i++){
		if(!ok[i]) continue;
		//sort(part[i].begin(), part[i].end());
		vector<ii> upds;
		for(auto it : part[i]){
	//		cout << i << " " << it.fi << " " << it.se << "\n";
			upds.pb({it.fi, 1});
			upds.pb({it.se + 1, -1});
		}
		sort(upds.begin(), upds.end());
		int lst = -oo, sum = 0;
		for(auto it : upds){
	//		cout << "OK " << sum << " " << lst << " " << it.fi << "\n";
			if(lst != -oo) ans += (it.fi - lst) * (sum != 0);
			sum += it.se;
			lst = it.fi;
		}
	//	cout << ans << "\n";
	}
	cout << ans << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen("device.inp", "r", stdin);
	//freopen("device.out", "w", stdout);
	process();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70648 KB Output is correct
2 Correct 40 ms 71064 KB Output is correct
3 Correct 38 ms 70924 KB Output is correct
4 Correct 40 ms 70740 KB Output is correct
5 Correct 39 ms 70744 KB Output is correct
6 Correct 43 ms 70740 KB Output is correct
7 Correct 39 ms 70772 KB Output is correct
8 Correct 35 ms 70668 KB Output is correct
9 Correct 35 ms 70740 KB Output is correct
10 Correct 34 ms 70720 KB Output is correct
11 Correct 34 ms 70740 KB Output is correct
12 Correct 35 ms 70664 KB Output is correct
13 Correct 37 ms 70756 KB Output is correct
14 Correct 37 ms 70660 KB Output is correct
15 Correct 36 ms 70868 KB Output is correct
16 Correct 39 ms 71008 KB Output is correct
17 Correct 92 ms 73212 KB Output is correct
18 Correct 40 ms 70696 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70756 KB Output is correct
2 Correct 36 ms 70760 KB Output is correct
3 Correct 36 ms 70764 KB Output is correct
4 Correct 36 ms 70728 KB Output is correct
5 Correct 38 ms 70752 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70700 KB Output is correct
2 Correct 36 ms 70936 KB Output is correct
3 Correct 36 ms 70708 KB Output is correct
4 Correct 35 ms 70896 KB Output is correct
5 Correct 750 ms 198364 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 744 ms 169504 KB Output is correct
3 Correct 1658 ms 316880 KB Output is correct
4 Correct 1684 ms 318684 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 744 ms 169504 KB Output is correct
3 Correct 1658 ms 316880 KB Output is correct
4 Correct 1684 ms 318684 KB Output is correct
5 Correct 34 ms 70692 KB Output is correct
6 Correct 1234 ms 243676 KB Output is correct
7 Correct 636 ms 122100 KB Output is correct
8 Correct 1249 ms 243612 KB Output is correct
9 Correct 1251 ms 243728 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct
2 Correct 744 ms 169504 KB Output is correct
3 Correct 1658 ms 316880 KB Output is correct
4 Correct 1684 ms 318684 KB Output is correct
5 Correct 34 ms 70680 KB Output is correct
6 Correct 138 ms 86716 KB Output is correct
7 Correct 153 ms 93568 KB Output is correct
8 Correct 162 ms 93564 KB Output is correct
9 Correct 161 ms 93600 KB Output is correct
10 Correct 117 ms 84256 KB Output is correct
11 Correct 152 ms 93604 KB Output is correct
12 Correct 153 ms 93580 KB Output is correct
13 Correct 155 ms 93540 KB Output is correct
14 Correct 97 ms 76896 KB Output is correct
15 Correct 124 ms 86744 KB Output is correct
16 Correct 88 ms 76596 KB Output is correct
17 Correct 160 ms 93824 KB Output is correct
18 Correct 1166 ms 243668 KB Output is correct
19 Correct 1313 ms 243752 KB Output is correct
20 Correct 1421 ms 243920 KB Output is correct
21 Correct 150 ms 93564 KB Output is correct
22 Correct 163 ms 93500 KB Output is correct
23 Correct 326 ms 129220 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70668 KB Output is correct
2 Correct 88 ms 73024 KB Output is correct
3 Correct 82 ms 72820 KB Output is correct
4 Correct 651 ms 133264 KB Output is correct
5 Correct 85 ms 73776 KB Output is correct
6 Correct 90 ms 73460 KB Output is correct
7 Correct 97 ms 73724 KB Output is correct
8 Correct 110 ms 75608 KB Output is correct
9 Correct 91 ms 75508 KB Output is correct
10 Correct 117 ms 72480 KB Output is correct
11 Correct 88 ms 73020 KB Output is correct
12 Correct 81 ms 72872 KB Output is correct
13 Correct 85 ms 74604 KB Output is correct
14 Correct 505 ms 87364 KB Output is correct
15 Correct 84 ms 73036 KB Output is correct
16 Correct 591 ms 92696 KB Output is correct
17 Correct 670 ms 135052 KB Output is correct
18 Correct 37 ms 70720 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70648 KB Output is correct
2 Correct 40 ms 71064 KB Output is correct
3 Correct 38 ms 70924 KB Output is correct
4 Correct 40 ms 70740 KB Output is correct
5 Correct 39 ms 70744 KB Output is correct
6 Correct 43 ms 70740 KB Output is correct
7 Correct 39 ms 70772 KB Output is correct
8 Correct 35 ms 70668 KB Output is correct
9 Correct 35 ms 70740 KB Output is correct
10 Correct 34 ms 70720 KB Output is correct
11 Correct 34 ms 70740 KB Output is correct
12 Correct 35 ms 70664 KB Output is correct
13 Correct 37 ms 70756 KB Output is correct
14 Correct 37 ms 70660 KB Output is correct
15 Correct 36 ms 70868 KB Output is correct
16 Correct 39 ms 71008 KB Output is correct
17 Correct 92 ms 73212 KB Output is correct
18 Correct 40 ms 70696 KB Output is correct
19 Correct 36 ms 70756 KB Output is correct
20 Correct 36 ms 70760 KB Output is correct
21 Correct 36 ms 70764 KB Output is correct
22 Correct 36 ms 70728 KB Output is correct
23 Correct 38 ms 70752 KB Output is correct
24 Correct 33 ms 70700 KB Output is correct
25 Correct 36 ms 70936 KB Output is correct
26 Correct 36 ms 70708 KB Output is correct
27 Correct 35 ms 70896 KB Output is correct
28 Correct 750 ms 198364 KB Output is correct
29 Correct 34 ms 70740 KB Output is correct
30 Correct 744 ms 169504 KB Output is correct
31 Correct 1658 ms 316880 KB Output is correct
32 Correct 1684 ms 318684 KB Output is correct
33 Correct 34 ms 70692 KB Output is correct
34 Correct 1234 ms 243676 KB Output is correct
35 Correct 636 ms 122100 KB Output is correct
36 Correct 1249 ms 243612 KB Output is correct
37 Correct 1251 ms 243728 KB Output is correct
38 Correct 34 ms 70680 KB Output is correct
39 Correct 138 ms 86716 KB Output is correct
40 Correct 153 ms 93568 KB Output is correct
41 Correct 162 ms 93564 KB Output is correct
42 Correct 161 ms 93600 KB Output is correct
43 Correct 117 ms 84256 KB Output is correct
44 Correct 152 ms 93604 KB Output is correct
45 Correct 153 ms 93580 KB Output is correct
46 Correct 155 ms 93540 KB Output is correct
47 Correct 97 ms 76896 KB Output is correct
48 Correct 124 ms 86744 KB Output is correct
49 Correct 88 ms 76596 KB Output is correct
50 Correct 160 ms 93824 KB Output is correct
51 Correct 1166 ms 243668 KB Output is correct
52 Correct 1313 ms 243752 KB Output is correct
53 Correct 1421 ms 243920 KB Output is correct
54 Correct 150 ms 93564 KB Output is correct
55 Correct 163 ms 93500 KB Output is correct
56 Correct 326 ms 129220 KB Output is correct
57 Correct 39 ms 70668 KB Output is correct
58 Correct 88 ms 73024 KB Output is correct
59 Correct 82 ms 72820 KB Output is correct
60 Correct 651 ms 133264 KB Output is correct
61 Correct 85 ms 73776 KB Output is correct
62 Correct 90 ms 73460 KB Output is correct
63 Correct 97 ms 73724 KB Output is correct
64 Correct 110 ms 75608 KB Output is correct
65 Correct 91 ms 75508 KB Output is correct
66 Correct 117 ms 72480 KB Output is correct
67 Correct 88 ms 73020 KB Output is correct
68 Correct 81 ms 72872 KB Output is correct
69 Correct 85 ms 74604 KB Output is correct
70 Correct 505 ms 87364 KB Output is correct
71 Correct 84 ms 73036 KB Output is correct
72 Correct 591 ms 92696 KB Output is correct
73 Correct 670 ms 135052 KB Output is correct
74 Correct 37 ms 70720 KB Output is correct
75 Correct 39 ms 70660 KB Output is correct
76 Correct 37 ms 70712 KB Output is correct
77 Correct 37 ms 70776 KB Output is correct
78 Correct 39 ms 70840 KB Output is correct
79 Correct 43 ms 72012 KB Output is correct
80 Correct 501 ms 90580 KB Output is correct
81 Correct 688 ms 134604 KB Output is correct
82 Correct 1212 ms 243184 KB Output is correct
83 Correct 1185 ms 243040 KB Output is correct
84 Correct 1210 ms 243376 KB Output is correct
85 Correct 1326 ms 243312 KB Output is correct
86 Correct 333 ms 132632 KB Output is correct
87 Correct 37 ms 70740 KB Output is correct