QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #550452 | #9252. Penguins in Refrigerator | ucup-team896# | WA | 42ms | 45656kb | C++14 | 2.0kb | 2024-09-07 12:54:27 | 2024-09-07 12:54:27 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
#define int LL
const int N=1e6+5,P=1e9+7;
int n,W,ans=1;
vector<int>G[N];
set<pair<int,int>>Y;
vector<pair<int,int>>X;
priority_queue<int,vector<int>,greater<int>>Q;
int p[N],q[N],a[N],A[N],st[N],L[N],R[N],d[N];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>W;
for(int i=1;i<=n;++i)cin>>p[i],q[p[i]]=i;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)A[p[i]]=a[i];
for(int i=1,top=0;i<=n;++i)
if(A[i]<=W/2){
int z=0;
for(int l=1,r=top;l<=r;){
const int mid=(l+r)>>1;
if(A[st[mid]]+A[i]>W)z=mid,l=mid+1;
else r=mid-1;
}
if(z)L[i]=st[z];
else L[i]=0;
}
else{
for(;top&&A[st[top]]<=A[i];--top);
st[++top]=i;
}
for(int i=n,top=0;i>=1;--i)
if(A[i]<=W/2){
int z=0;
for(int l=1,r=top;l<=r;){
const int mid=(l+r)>>1;
if(A[st[mid]]+A[i]>W)z=mid,l=mid+1;
else r=mid-1;
}
if(z)R[i]=st[z];
else R[i]=n+1;
}
else{
for(;top&&A[st[top]]<=A[i];--top);
st[++top]=i;
}
Y.emplace(0,0);
for(int i=1;i<=n;++i)
if(A[i]<=W/2)X.emplace_back(L[i],R[i]);
else Y.emplace(i,1);
Y.emplace(n+1,1);
sort(X.begin(),X.end(),[&](pair<int,int>x,pair<int,int>y){
return x.second-x.first<y.second-y.first;
});
for(auto [l,r]:X){
int c=0;
auto itl=next(Y.lower_bound(make_pair(l,-1))),itr=itl;
while(itr!=Y.end()&&itr->first<=r)c+=itr->second,++itr;
Y.erase(itl,itr);
ans=1ll*ans*c%P;
Y.emplace(r,c+1);
}
cout<<ans<<'\n';
for(int i=1,j=0;i<=n;++i)
if(A[i]<=W/2){
if(L[i]>=1)G[q[i]].emplace_back(q[L[i]]);
if(R[i]<=n)G[q[R[i]]].emplace_back(q[i]);
}
else{
if(j)G[q[i]].emplace_back(q[j]);
j=i;
}
for(int i=1;i<=n;++i)for(auto j:G[i])++d[j];
for(int i=1;i<=n;++i)if(!d[i])Q.emplace(i);
for(int i=1;i<=n;++i){
int u=Q.top();Q.pop();
cout<<u<<" \n"[i==n];
for(auto v:G[u])if(!--d[v])Q.emplace(v);
}
return 0;
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 41840kb
input:
5 10 1 2 3 4 5 6 5 3 9 2
output:
3 5 4 2 1 3
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 35968kb
input:
5 10 1 2 3 4 5 2 4 3 3 8
output:
30 1 5 2 3 4
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 6ms
memory: 39452kb
input:
5 10 1 2 3 4 5 2 3 4 5 1
output:
120 1 2 3 4 5
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 3ms
memory: 35564kb
input:
5 10 1 2 3 4 5 2 3 4 5 6
output:
60 1 2 3 5 4
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 25ms
memory: 42520kb
input:
100000 96 1996 78922 45321 68844 32404 82013 66552 81163 17216 48170 35495 56660 13480 43118 23173 47257 50168 87069 26167 67231 31758 25694 61063 56642 8923 7727 54528 96554 38964 7604 6822 16256 45300 58869 31359 48638 87645 14779 81505 59585 89293 9291 7002 31810 84701 77648 78295 42595 11394 479...
output:
457992974 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
result:
ok 2 lines
Test #6:
score: -100
Wrong Answer
time: 42ms
memory: 45656kb
input:
100000 84 93330 3894 94859 22134 49668 30606 26739 82976 76701 56323 75537 7626 87226 20857 98177 21811 70827 75898 8111 48223 26186 64222 63002 79024 19126 41638 1048 43857 25379 19764 60207 27675 77665 66327 6274 34861 30287 13449 64505 51490 5804 65843 49014 85795 12365 31565 34411 71697 66568 28...
output:
120390347 1358 17609 18290 26501 35681 58859 60458 66474 79326 81095 92556 23867 99165 28710 12244 72282 11204 11811 19728 29952 34067 37825 67861 84745 87426 76518 4067 12286 25502 46675 50885 14477 51062 57578 58025 89917 98967 83739 33176 79256 49220 64892 1209 25824 32650 33123 50323 54679 64502...
result:
wrong answer 1st lines differ - expected: '524727018', found: '120390347'