이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
int MOD = 1e9+7,inf = 2e18;
const int N = 1e5+50,Q = 2e5+50;
struct DSU {
vi dad,sz;
DSU(int nn) {
dad.resize(nn+1);
iota(all(dad),0ll);
sz.assign(nn+1,1);
}
int find(int x) {
if (x == dad[x]) return x;
return dad[x] = find(dad[x]);
}
void unite(int x,int y) {
int a = find(x),b = find(y);
if (a == b) return;
if (sz[a] < sz[b]) swap(a,b);
dad[b] = a;
sz[a]+=sz[b];
}
};
vi have[10000001];
int orig[10000001];
struct Edge {
int u,v;
};
void solve() {
int n;
cin >> n;
vi p(n);
for (int i=0;i<n;i++) cin >> p[i];
sort(p.begin(),p.end());
vi pp;
for (int i = 0;i<n;i++) if (!i || p[i] != p[i-1]) pp.push_back(p[i]);
n = pp.size();
for (int i = 0;i<n;i++) {
orig[pp[i]] = i+1;
}
int sm = 0;
for (int i = 1;i<n;i++) sm+=pp[i]%pp[i-1];
vi collect;
vector<Edge> edges;
int lasttake[n+1]{0};
long long ans = 0;
for (int i = 1;i<=10000000;i++) {
for (auto it : have[i]) {
if (!lasttake[it]) collect.push_back(it);
lasttake[it] = i;
}
//cout << "I" sp i << endl;
if (orig[i]) {
if (!lasttake[orig[i]]) collect.push_back(orig[i]);
lasttake[orig[i]] = i;
have[i].push_back(orig[i]);
//for (auto it : collect) cout << it.ff sp it.ss << '\n';
for (auto it : collect) {
if (it != orig[i]) {
if (i-lasttake[it] <= sm) edges.push_back(Edge{it,orig[i]});
}
}
for (auto it : collect) lasttake[it] = 0;
collect.clear();
if (!lasttake[orig[i]]) collect.push_back(orig[i]);
lasttake[orig[i]] = i;
}
for (auto it : have[i]) {
if (i+pp[it-1] <= 10000000) have[i+pp[it-1]].push_back(it);
}
have[i].clear();
}
sort(all(edges),[&](const Edge& e1,const Edge& e2) {
return pp[e1.v-1]-pp[e1.u-1] < pp[e2.v-1]-pp[e2.u-1];
});
DSU dsu(n);
for (auto& it : edges) {
if (dsu.find(it.u) != dsu.find(it.v)) {
dsu.unite(it.u,it.v);
ans+=pp[it.v-1]-pp[it.u-1];
}
}
cout << ans << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
컴파일 시 표준 에러 (stderr) 메시지
sirni.cpp:12:23: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
12 | int MOD = 1e9+7,inf = 2e18;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |