Submission #1004224

#TimeUsernameProblemLanguageResultExecution timeMemory
1004224TahirAliyevSirni (COCI17_sirni)C++17
140 / 140
2127 ms731948 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long #define ll long long #define pii pair<int, int> #define all(v) v.begin(), v.end() #define oo 1e9 const int MAX = 1e5 + 5, MX = 1e7 + 7; int n; int arr[MAX]; int nxt[MX]; vector<pii> E[MX]; int par[MAX]; void init(){ for(int i = 0; i < MAX; i++) par[i] = -1; } int get(int i){ if(par[i] < 0) return i; return par[i] = get(par[i]); } bool unite(int u, int v){ u = get(u), v = get(v); if(u == v) return 0; if(-par[u] < -par[v]) swap(u, v); par[u] += par[v]; par[v] = u; return 1; } void solve(){ cin >> n; init(); for(int i = 1; i <= n; i++){ cin >> arr[i]; if(nxt[arr[i]]) unite(i, nxt[arr[i]]); nxt[arr[i]] = i; } int cur = 0; for(int i = MX - 1; i >= 1; i--){ if(nxt[i]) cur = nxt[i]; nxt[i] = cur; } for(int i = 1; i <= n; i++){ if(nxt[arr[i] + 1] && arr[nxt[arr[i] + 1]] < 2 * arr[i]) E[arr[nxt[arr[i] + 1]] - arr[i]].push_back({i, nxt[arr[i] + 1]}); for(int j = 2 * arr[i]; j < MX; j += arr[i]){ if(nxt[j] && (arr[nxt[j]] < j + arr[i])) E[arr[nxt[j]] - j].push_back({i, nxt[j]}); } } ll ans = 0; for(int i = 0; i < MX; i++){ for(auto a : E[i]){ if(unite(a.first, a.second)) ans += i; } } cout << ans << '\n'; } signed main(){ // ios::sync_with_stdio(0); // cin.tie(0); // cout.tie(0); int t = 1; while(t--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...