oj.uz

Submission #489892

# Submission time Handle Problem Language Result Execution time Memory
489892 2021-11-25T02:56:46 Z 8e7 Sirni (COCI17_sirni) C++17
140 / 140
 4262 ms 244632 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 100005
#define maxc 10000005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
bool rig[maxc], lef[maxc];
int dis[maxn], ind[maxc];
bool found[maxn];
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> a;
vector<int> from[maxn];
set<int> se;
int n;
void upd(int x, int p) {
	auto checkbig = [&] (int i) {
		auto it = se.lower_bound(i);
		if (it != se.end()) {
			int id = ind[*it];
			if (a[id] - i < dis[id]) {
				dis[id] = a[id] - i;	
				pq.push({dis[id], id});
			}
		}
	};
	for (int i = (maxc-1) - ((maxc-1) % x);i >= x;i -= x) {
		if (!rig[i]) {
			rig[i] = 1;
			checkbig(i);
		}
	}
	checkbig(x);
	for (auto id:from[p]) {
		if (x % a[id] < dis[id] && !found[id]) {
			dis[id] = x % a[id];
			pq.push({dis[id], id});
		}	
	}
}
int main() {
	io
	cin >> n;
	a.resize(n, 0);
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	a.resize(int(unique(a.begin(), a.end()) - a.begin()));
	n = a.size();
	dis[0] = 0;
	found[0] = 1;
	for (int i = 1;i < n;i++) {
		dis[i] = 1<<30, se.insert(a[i]);
		ind[a[i]] = i;
		int prv = 0;
		for (int j = a[i];j < maxc;j += a[i]) {
			int id = lower_bound(a.begin(), a.end(), j) - a.begin();
			if (id < n && id != prv) {
				from[id].push_back(i);
			}
			prv = id;
		}
		int id = upper_bound(a.begin(), a.end(), a[i]) - a.begin();
		if (id < n) from[id].push_back(i);
	}
	upd(a[0], 0);
	int ans = 0;
	while (pq.size()) {
		pii cur = pq.top();pq.pop();
		if (cur.ff != dis[cur.ss] || found[cur.ss]) continue;
		ans += cur.ff;
		found[cur.ss] = 1;
		se.erase(a[cur.ss]);
		upd(a[cur.ss], cur.ss);	
	}
	cout << ans << endl;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14924 KB Output is correct
2 Correct 116 ms 15452 KB Output is correct
3 Correct 12 ms 16460 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 12556 KB Output is correct
2 Correct 693 ms 13444 KB Output is correct
3 Correct 11 ms 16460 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15564 KB Output is correct
2 Correct 10 ms 11004 KB Output is correct
3 Correct 11 ms 16504 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 30440 KB Output is correct
2 Correct 2096 ms 46768 KB Output is correct
3 Correct 1182 ms 31364 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 18608 KB Output is correct
2 Correct 887 ms 28532 KB Output is correct
3 Correct 1246 ms 27420 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1592 ms 38444 KB Output is correct
2 Correct 2385 ms 52052 KB Output is correct
3 Correct 1079 ms 31820 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 18480 KB Output is correct
2 Correct 2358 ms 49660 KB Output is correct
3 Correct 1053 ms 30784 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 650 ms 67904 KB Output is correct
2 Correct 3230 ms 204864 KB Output is correct
3 Correct 729 ms 69352 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 66748 KB Output is correct
2 Correct 4262 ms 244632 KB Output is correct
3 Correct 760 ms 70380 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 49760 KB Output is correct
2 Correct 3681 ms 224436 KB Output is correct
3 Correct 1148 ms 32080 KB Output is correct