#include <bits/stdc++.h>
//#include <iostream>
//#include <vector>
#define s second
#define pb push_back
#define f first
using namespace std;
const int N = 100005,M = 10000005;
int p[N],ans,m[M];
vector <pair<int,int>> w[M];
vector <pair<int,int>> d;
int P(int x){
if (x == p[x]) return x;
return p[x] = P(p[x]);
}
void dsu(int a,int b,int c){
int pa = P(a),pb = P(b);
if (pa == pb) return;
ans += c;
if (pa < pb) swap(pa,pb);
p[pb] = pa;
}
int main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
for (int i = 1; i <= n; i++){
int a;
cin>>a;
p[i] = i;
d.pb({a,i});
}
sort(d.begin(),d.end());
int r = d.size() - 1;
m[10000001] = -1;
for (int i = 1e7; i >= 1; i--){
m[i] = m[i + 1];
while (r >= 0 && i <= d[r].f)
m[i] = r--;
}
for (int y = 0; y < n; y++){
if (y + 1 < n && d[y+1].f < 2*d[y].f)
w[d[y+1].f - d[y].f].pb({y,y + 1});
if (y > 0 && d[y].f == d[y - 1].f) continue;
for (int j = 2*d[y].f; j <= 1e7; j += d[y].f)
if (m[j] >= 0 && d[m[j]].f - d[y].f < j)
w[d[m[j]].f - j].pb({y,m[j]});
}
for (int i = 0; i <= 1e7; i++){
for (int j = 0; j < w[i].size(); j++){
int x = w[i][j].f,y = w[i][j].s;
dsu(x,y,i);
}
}
cout<<ans;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int j = 0; j < w[i].size(); j++){
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
174 ms |
274384 KB |
Output is correct |
2 |
Correct |
194 ms |
276820 KB |
Output is correct |
3 |
Correct |
165 ms |
274532 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
205 ms |
274348 KB |
Output is correct |
2 |
Correct |
367 ms |
274964 KB |
Output is correct |
3 |
Correct |
165 ms |
274448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
175 ms |
274540 KB |
Output is correct |
2 |
Correct |
160 ms |
274332 KB |
Output is correct |
3 |
Correct |
171 ms |
274656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
339 ms |
286484 KB |
Output is correct |
2 |
Correct |
656 ms |
312176 KB |
Output is correct |
3 |
Correct |
357 ms |
290824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
181 ms |
276172 KB |
Output is correct |
2 |
Correct |
540 ms |
298312 KB |
Output is correct |
3 |
Correct |
383 ms |
286464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
515 ms |
297764 KB |
Output is correct |
2 |
Correct |
752 ms |
326736 KB |
Output is correct |
3 |
Correct |
338 ms |
289268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
299 ms |
278508 KB |
Output is correct |
2 |
Correct |
776 ms |
321824 KB |
Output is correct |
3 |
Correct |
334 ms |
288668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
287768 KB |
Output is correct |
2 |
Correct |
1396 ms |
483964 KB |
Output is correct |
3 |
Correct |
303 ms |
290148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
303 ms |
288168 KB |
Output is correct |
2 |
Correct |
3016 ms |
575096 KB |
Output is correct |
3 |
Correct |
293 ms |
294824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
190 ms |
276848 KB |
Output is correct |
2 |
Correct |
3362 ms |
570564 KB |
Output is correct |
3 |
Correct |
358 ms |
291008 KB |
Output is correct |