QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291117 | #3241. 最小公倍树 | MoRanSky | AC ✓ | 458ms | 145464kb | C++23 | 1.8kb | 2023-12-26 04:55:30 | 2023-12-26 04:55:31 |
Judging History
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'