#include <bits/stdc++.h>
// #define int int64_t //be careful about this
using namespace std;
#define vt vector
#define ar array
#define pr pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define fr(i,a,b) for(int i = a; i < b; ++i)
#define rf(i,a,b) for(int i = b-1; i >= a; --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
namespace IN{
template<class T> void re(vector<T> &A);
template<class S,class T> void re(pair<S,T> &A);
template<class T,size_t N> void re(array<T,N> &A);
template<class T> void re(T& x){
cin >> x;}
template<class H, class... T> void re(H& h, T&... t){
re(h); re(t...);}
template<class T> void re(vector<T> &A){
for(auto& x : A) re(x);}
template<class S,class T> void re(pair<S,T> &A){
re(A.first); re(A.second);}
template<class T,size_t N> void re(array<T,N> &A){
for(int i = 0; i < N; ++i) re(A[i]);}
}
namespace OUT{
template<class T>
void __p(const T& a){ cout<<a; }
template<class T, class F>
void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
template<class T, size_t N>
void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
template<class T>
void __p(const vector<T>& a){
cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
template<class T, class ...Arg>
void __p(T a1, Arg ...a){__p(a1); __p(a...); }
template<class Arg1>
void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
template<class Arg1, class ... Args>
void __f(const char *ss, Arg1 &&arg1, Args &&... args){
int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
#define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
}
namespace FUNC{
void IO(string s = ""){
ios_base::sync_with_stdio(NULL);
cin.tie(nullptr);
cout.precision(20);
cout << fixed;
if(!s.empty()){
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
}
const auto start_time = chrono::high_resolution_clock::now();
void output_run_time(){
// will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
auto end_time = chrono::high_resolution_clock::now();
chrono::duration<double> diff = end_time-start_time;
cout << "\n\n\nTime Taken : " << diff.count();
#endif
}
template<class T> bool ckmin(T& a, const T& b){
return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, const T& b){
return a < b ? a = b, true : false; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int L, int R){
return uniform_int_distribution<int>(L,R)(rng); }
template<class T> int sz(const T& x){
return int(x.size()); }
template<class T> int lb(const vector<T>& vec,const T& val){
return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }
template<class T> int ub(const vector<T>& vec,const T& val){
return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }
constexpr int dx[4] = {1,0,-1,0};
constexpr int dy[4] = {0,1,0,-1};
constexpr char dr[4] = {'D','R','U','L'};
constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
constexpr int INF = 2e9;
template<class T>
vector<T> V(int n,T val){
return vector<T> (n,val);
}
template<class T>
vector<vector<T>> V(int n,int m,T val){
return vector<vector<T>> (n,vector<T> (m,val));
}
template<class T>
vector<vector<vector<T>>> V(int n,int m,int k,T val){
return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
}
}
using namespace IN;
using namespace OUT;
using namespace FUNC;
struct DSU {
int n, z;
// root node: -1 * component size
// otherwise: parent
vector<int> parent_or_size;
DSU(int n) : n(n), parent_or_size(n, -1), z(n) {}
bool merge(int a, int b){
int x = leader(a), y = leader(b);
if(x == y)
return false;
if(-parent_or_size[x] < -parent_or_size[y])
swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
z--;
return true;
}
bool same(int a, int b){
return leader(a) == leader(b);
}
int leader(int a){
if(parent_or_size[a] < 0)
return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a){
return -parent_or_size[leader(a)];
}
vector<vector<int>> groups(){
vector<int> leader_buf(n), group_size(n);
for(int i = 0; i < n; i++){
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
vector<vector<int>> result(n);
for(int i = 0; i < n; i++){
result[i].reserve(group_size[i]);
}
for(int i = 0; i < n; i++){
result[leader_buf[i]].push_back(i);
}
result.erase(remove_if(result.begin(), result.end(),[&](const auto& v){return v.empty(); }),result.end());
return result;
}
int comp(){
return z;
}
};
template<class T>
struct BasicSegmentTree {
const T ID = {INF,-1};
T comb(T a, T b){
return a.f == b.f ? (a.s > b.s ? b : a) : (a.f > b.f ? b : a);
}
int n; vector<T> seg;
void init(int _n){
n = _n; seg.assign(2 * n,ID);
}
void pull(int p){
seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
}
void upd(int p, T val){ // update val at position p
seg[p += n] = val;
for(p /= 2; p; p /= 2) pull(p);
}
T query(int l, int r){ // query on interval [l, r]
T ra = ID, rb = ID;
for(l += n, r += n+1; l < r; l /= 2, r /= 2){
if(l&1) ra = comb(ra,seg[l++]);
if(r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
signed main(){
IO();
int n;
re(n);
vt<int> p(n);
re(p);
sort(all(p));
p.erase(unique(all(p)),p.end());
n = sz(p);
int N = p.back();
BasicSegmentTree<pr<int,int>> st;
st.init(N+1);
fr(i,0,n){
st.upd(p[i],{p[i],i});
}
DSU dsu(n);
long long cost = 0;
while(dsu.comp() > 1){
auto groups = dsu.groups();
vt<int> find_w(n,INF), find_e(n,-1);
for(auto g : groups){
for(auto i : g)
st.upd(p[i],st.ID);
for(auto i : g){
for(int r = 0; r * p[i] <= N; r++){
auto [_,j] = st.query(r*p[i],min(N,(r+1)*p[i]-1));
if(j < 0)
continue;
int w = p[j]%p[i], u = dsu.leader(i), v = dsu.leader(j);
fr(_,0,2){
if(ckmin(find_w[u],w))
find_e[u] = v;
swap(u,v);
}
}
}
for(auto i : g)
st.upd(p[i],{p[i],i});
}
fr(i,0,n){
if(find_e[i] >= 0){
if(dsu.merge(i,find_e[i]))
cost += find_w[i];
}
}
}
cout << cost;
// output_run_time();
return 0;
}
Compilation message
sirni.cpp: In constructor 'DSU::DSU(int)':
sirni.cpp:150:15: warning: 'DSU::parent_or_size' will be initialized after [-Wreorder]
150 | vector<int> parent_or_size;
| ^~~~~~~~~~~~~~
sirni.cpp:147:10: warning: 'int DSU::z' [-Wreorder]
147 | int n, z;
| ^
sirni.cpp:152:3: warning: when initialized here [-Wreorder]
152 | DSU(int n) : n(n), parent_or_size(n, -1), z(n) {}
| ^~~
sirni.cpp: In function 'void FUNC::IO(std::string)':
sirni.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
156792 KB |
Output is correct |
| 2 |
Correct |
1745 ms |
156228 KB |
Output is correct |
| 3 |
Correct |
78 ms |
156164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
468 KB |
Output is correct |
| 2 |
Correct |
4823 ms |
156620 KB |
Output is correct |
| 3 |
Correct |
106 ms |
156876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
156772 KB |
Output is correct |
| 2 |
Correct |
63 ms |
156624 KB |
Output is correct |
| 3 |
Correct |
73 ms |
156780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
631 ms |
22620 KB |
Output is correct |
| 2 |
Correct |
1041 ms |
22172 KB |
Output is correct |
| 3 |
Correct |
474 ms |
21472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
17100 KB |
Output is correct |
| 2 |
Correct |
1380 ms |
16972 KB |
Output is correct |
| 3 |
Correct |
495 ms |
13664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1193 ms |
22632 KB |
Output is correct |
| 2 |
Correct |
1483 ms |
22440 KB |
Output is correct |
| 3 |
Correct |
456 ms |
22548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
5844 KB |
Output is correct |
| 2 |
Correct |
1528 ms |
21260 KB |
Output is correct |
| 3 |
Correct |
441 ms |
21872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1180 ms |
163788 KB |
Output is correct |
| 2 |
Execution timed out |
5079 ms |
163768 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1118 ms |
163888 KB |
Output is correct |
| 2 |
Execution timed out |
5063 ms |
162640 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
318 ms |
158236 KB |
Output is correct |
| 2 |
Execution timed out |
5097 ms |
162120 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
