#pragma GCC optimize("Ofast,unroll-loops,O3")
#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
#define C 10000001
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int vis[C+3];
int n,arr[N];
vector<int>vt;
vector<pii>edge[C];
struct dsu{
int boss[N],sz[N];
void init(int n){
for (int i=1;i<=n;i++){
boss[i]=i; sz[i]=1;
}
}
int find(int x){
if (boss[x]==x) return x;
return boss[x]=find(boss[x]);
}
void Merge(int a,int b){
int ra=find(a),rb=find(b);
if (ra==rb) return;
if (sz[ra]<sz[rb]) swap(ra,rb);
sz[ra]+=sz[rb];
boss[rb]=ra;
}
}d;
signed main(){
fast
cin>>n;
for (int i=1;i<=n;i++){
cin>>arr[i];
vt.push_back(arr[i]);
}
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
int mx=vt.back();
for (int i=0;i<vt.size();i++)
vis[vt[i]]=i+1;
for (int i=mx;i>=1;i--){
if (vis[i]) continue;
vis[i]=vis[i+1];
}
for (int i=0;i<vt.size();i++){
int now=vt[i];
if (i!=(int)(vt.size())-1){
edge[vt[vis[now+1]-1]%now].push_back({i+1,vis[now+1]});
}
for (int j=now;j<=mx;j+=now){
edge[vt[vis[j]-1]%now].push_back({i+1,vis[j]});
}
}
int ans=0;
d.init(n);
for (int i=0;i<mx;i++){
for (auto j:edge[i]){
if (d.find(j.x)!=d.find(j.y)){
ans+=i;
d.Merge(j.x,j.y);
}
}
}
cout<<ans<<'\n';
}
Compilation message
sirni.cpp:2:88: warning: bad option '-favx' to pragma 'optimize' [-Wpragmas]
2 | #pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
| ^
sirni.cpp:2:88: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse2' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse3' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fssse3' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fsse4' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fpopcnt' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fabm' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-fmmx' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-ffma' to pragma 'optimize' [-Wpragmas]
sirni.cpp:2:88: warning: bad option '-ftune=native' to pragma 'optimize' [-Wpragmas]
sirni.cpp:23:20: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
23 | void init(int n){
| ^
sirni.cpp:23:20: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:23:20: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
28 | int find(int x){
| ^
sirni.cpp:28:19: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:28:19: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
32 | void Merge(int a,int b){
| ^
sirni.cpp:32:27: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:32:27: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-favx' to attribute 'optimize' [-Wattributes]
40 | signed main(){
| ^
sirni.cpp:40:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse2' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fssse3' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fsse4' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fpopcnt' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fabm' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-fmmx' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-ffma' to attribute 'optimize' [-Wattributes]
sirni.cpp:40:13: warning: bad option '-ftune=native' to attribute 'optimize' [-Wattributes]
sirni.cpp: In function 'int main()':
sirni.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i=0;i<vt.size();i++)
| ~^~~~~~~~~~
sirni.cpp:56:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i=0;i<vt.size();i++){
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
189 ms |
274376 KB |
Output is correct |
| 2 |
Correct |
267 ms |
303716 KB |
Output is correct |
| 3 |
Correct |
208 ms |
274492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
123 ms |
235264 KB |
Output is correct |
| 2 |
Correct |
1353 ms |
668776 KB |
Output is correct |
| 3 |
Correct |
197 ms |
275148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
188 ms |
274368 KB |
Output is correct |
| 2 |
Correct |
189 ms |
274304 KB |
Output is correct |
| 3 |
Correct |
192 ms |
274616 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
187 ms |
251680 KB |
Output is correct |
| 2 |
Correct |
274 ms |
279380 KB |
Output is correct |
| 3 |
Correct |
288 ms |
264380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
139 ms |
241484 KB |
Output is correct |
| 2 |
Correct |
209 ms |
264040 KB |
Output is correct |
| 3 |
Correct |
170 ms |
249608 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
213 ms |
263588 KB |
Output is correct |
| 2 |
Correct |
312 ms |
297244 KB |
Output is correct |
| 3 |
Correct |
197 ms |
260672 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
139 ms |
240336 KB |
Output is correct |
| 2 |
Correct |
294 ms |
297948 KB |
Output is correct |
| 3 |
Correct |
206 ms |
262340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
254 ms |
290364 KB |
Output is correct |
| 2 |
Correct |
1303 ms |
635292 KB |
Output is correct |
| 3 |
Correct |
266 ms |
293900 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
275 ms |
294828 KB |
Output is correct |
| 2 |
Correct |
1944 ms |
747944 KB |
Output is correct |
| 3 |
Correct |
442 ms |
348952 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
214 ms |
277156 KB |
Output is correct |
| 2 |
Correct |
1688 ms |
636436 KB |
Output is correct |
| 3 |
Correct |
216 ms |
265008 KB |
Output is correct |
