QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #476982 | #7749. A Simple MST Problem | zttttt | WA | 811ms | 47720kb | C++14 | 3.4kb | 2024-07-13 22:09:15 | 2024-07-13 22:09:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],primes[N],mp[N],zxzys[N],cnt,mul[N],pos[N],l[N],pos1[N],r[N],cntt[N],w[N],mpp[N],rd[N];
int main(){
//puts("fuck");
for(int i=2;i<=1000000;i++){
if(st[i]==0){
mp[i]=1;
cnt++;
//cout<<i<<endl;
primes[cnt]=i;
for(int j=1;j*i<=1000000;j++){
st[j*i]=1;
zxzys[j*i]=i;
}
}
}
// puts("fuck");
// s[1].insert(1);
for(int i=2;i<=1000000;i++){
int i1=i;
set<int>s;
while(i1!=1){
s.insert(zxzys[i1]);
int i2=i1;
while(i2%zxzys[i1]==0){
i2/=zxzys[i1];
}
i1=i2;
}
w[i]=s.size();
int zt=1;
for(auto j:s){
zt*=j;
}
mul[i]=zt;
//if(i>30)break;
}
//return 0;
//cout<<w[30]<<endl;
//puts("fuck");
// for(int i=1;i<=1000000;i++){
// int zt=1;
// for(auto j:s[i]){
// zt*=j;
// }
// mul[i]=zt;
// }
// puts("fuck");
// return 0;
for(int i=2;i<=N-10;i++){
set<int>s;
s.insert(1);
//cout<<i<<" "<<s1[i].size()<<endl;
int zt=mul[i];
// cout<<i<<" "<<zt<<" "<<mul[i]<<endl;
// cout<<i<<endl;
while(zt!=1){
int cnt1=0;
for(auto j:s){
//int cnt1=0;
cnt1++;
cntt[cnt1]=j;
}
for(int j=1;j<=cnt1;j++){
s.insert(cntt[j]*zxzys[zt]);
}
int ztt=zt;
while(ztt%zxzys[zt]==0){
ztt/=zxzys[zt];
}
zt=ztt;
}
//puts("fuck");
//if(i==30)cout<<s1[i].size()<<endl;
for(auto j:s){
// cout<<s1[i].size()<<endl;
// cout<<j<<endl;
if(pos[j])l[i]=max(l[i],pos[j]);
}
// if(i==30){
// cout<<l[i]<<endl;
// return 0;
// }
pos[mul[i]]=i;
}
// puts("fuck");
for(int i=N-10;i>=2;i--){
r[i]=1e9;
set<int>s;
s.insert(1);
//cout<<i<<" "<<s1[i].size()<<endl;
int zt=mul[i];
//cout<<i<<" "<<mul[i]<<endl;
// cout<<i<<" "<<zt<<" "<<mul[i]<<endl;
// cout<<i<<endl;
while(zt!=1){
int cnt1=0;
for(auto j:s){
//int cnt1=0;
cnt1++;
cntt[cnt1]=j;
}
for(int j=1;j<=cnt1;j++){
s.insert(cntt[j]*zxzys[zt]);
}
int ztt=zt;
while(ztt%zxzys[zt]==0){
ztt/=zxzys[zt];
}
zt=ztt;
}
// puts("fuck");
//if(i==30)cout<<s2[i].size()<<endl;
for(auto j:s){
// cout<<s1[i].size()<<endl;
// if(i==30)cout<<j<<endl;
if(pos1[j])r[i]=min(r[i],pos1[j]);
}
// if(i==30){
// cout<<l[i]<<endl;
// return 0;
// }
pos1[mul[i]]=i;
}
//cout<<r[30]<<endl;
int t;
scanf("%d",&t);
while(t--){
int ans=0;
int l1,r1;
scanf("%d%d",&l1,&r1);
for(int i=l1;i<=r1;i++)rd[i]=0;
if(l1==1){
for(int i=2;i<=r1;i++)ans+=w[i];
cout<<ans<<endl;
continue;
}
int flag=0;
for(int i=l1;i<=r1;i++){
if(mp[i]){
flag=1;
break;
}
}
if(flag){
for(int i=l1;i<=r1;i++){
// cout<<i<<" "<<l[i]<<" "<<r[i]<<" "<<w[i]<<endl;
mpp[i]=0;
if(l[i]>=l1&&l[i]<=r1&&(rd[i]==0||mpp[l[i]]==0)){
//cout<<i<<" l "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
ans+=w[i];
mpp[i]=1;
rd[l[i]]=1;
}else{
if(r[i]>=l1&&r[i]<=r1&&(rd[i]==0||mpp[r[i]]==0)){
//cout<<i<<" r "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
ans+=w[i];
mpp[i]=1;
rd[r[i]]=1;
}
}
}
for(int i=l1;i<=r1;i++)
{
if(mpp[i]==0){
//cout<<i<<" s "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
ans+=w[i]+1;
}
}
ans-=2;
}else{
}
printf("%d\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 811ms
memory: 44568kb
input:
5 1 1 4 5 1 4 1 9 19 810
output:
0 2 3 9 1812
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 801ms
memory: 45132kb
input:
2 27 30 183704 252609
output:
8 223092
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 803ms
memory: 46820kb
input:
1 183704 252609
output:
223092
result:
ok single line: '223092'
Test #4:
score: 0
Accepted
time: 802ms
memory: 46624kb
input:
2 639898 942309 30927 34660
output:
983228 11512
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 809ms
memory: 47720kb
input:
3 21731 33468 46192 370315 1712 3753
output:
34608 948775 5299
result:
ok 3 lines
Test #6:
score: -100
Wrong Answer
time: 798ms
memory: 47284kb
input:
4 15237 67700 10918 86104 98287 116980 17432 23592
output:
148811 210973 60893 18704
result:
wrong answer 2nd lines differ - expected: '210927', found: '210973'