QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291117#3241. 最小公倍树MoRanSkyAC ✓458ms145464kbC++231.8kb2023-12-26 04:55:302023-12-26 04:55:31

Judging History

你现在查看的是最新测评结果

  • [2023-12-26 04:55:31]
  • 评测
  • 测评结果:AC
  • 用时:458ms
  • 内存:145464kb
  • [2023-12-26 04:55:30]
  • 提交

answer

// Skyqwq
#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 1e6 + 5;

int l, r, f[N], ex[N], cnt;

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

int t;

vector<int> d[N];

struct Node{
	int u, v, p;
	LL w;
	bool operator > (const Node &b) const {
		if (w != b.w) return w > b.w;
		if (u != b.u) return u > b.u;
		if (v != b.v) return v > b.v;
		return p > b.p;
	} 
};

priority_queue<Node, vector<Node>, greater<Node> > q;

set<int> m[N];

void inline ins(int x) {
	while (m[x].size() >= 2) {
		int A = *m[x].begin();
		int B = *(++m[x].begin());
		if (find(A) == find(B)) {
			m[x].erase(B);
		} else break;
	}
	
	if (m[x].size() < 2) return;
	int A = *m[x].begin();
	int B = *(++m[x].begin());
	q.push((Node){ A, B, x, (LL)A * B / x });
}
 
int main() {
	read(l), read(r);
	LL ans = 0;
	for (int i = l; i <= r; i++) f[i] = i;
	for (int i = 1; i <= r; i++) {
		for (int j = i; j <= r; j += i) {
			if (j >= l) {
				m[i].insert(j);
			}
		}
		ins(i);
	}

	while (cnt < r - l) {
		while (q.size()) {
			Node u = q.top();
			if (find(u.u) == find(u.v)) q.pop(), ins(u.p);
			else break;
		}
		Node u = q.top(); q.pop();
		f[find(u.u)] = find(u.v);
		ans += u.w;
		ins(u.p);
		++cnt;
	}
	cout << ans;
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 164ms
memory: 136572kb

input:

100000 200000

output:

171167496763057

result:

ok single line: '171167496763057'

Test #2:

score: 0
Accepted
time: 157ms
memory: 141452kb

input:

253276 353266

output:

927665531658996

result:

ok single line: '927665531658996'

Test #3:

score: 0
Accepted
time: 155ms
memory: 145456kb

input:

655914 755442

output:

5580601534791953

result:

ok single line: '5580601534791953'

Test #4:

score: 0
Accepted
time: 161ms
memory: 145464kb

input:

900000 1000000

output:

10250678499914055

result:

ok single line: '10250678499914055'

Test #5:

score: 0
Accepted
time: 8ms
memory: 74020kb

input:

99991 99991

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 170ms
memory: 136820kb

input:

99991 199982

output:

171132525371252

result:

ok single line: '171132525371252'

Test #7:

score: 0
Accepted
time: 8ms
memory: 75220kb

input:

100003 100003

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 12ms
memory: 73808kb

input:

666666 666667

output:

444444222222

result:

ok single line: '444444222222'

Test #9:

score: 0
Accepted
time: 458ms
memory: 130572kb

input:

1 99667

output:

4966805277

result:

ok single line: '4966805277'

Test #10:

score: 0
Accepted
time: 451ms
memory: 129176kb

input:

2 99248

output:

5373052945

result:

ok single line: '5373052945'

Test #11:

score: 0
Accepted
time: 155ms
memory: 144684kb

input:

798954 898945

output:

8177721171091522

result:

ok single line: '8177721171091522'