QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #551537 | #9252. Penguins in Refrigerator | ucup-team052# | WA | 48ms | 34068kb | C++23 | 2.2kb | 2024-09-07 17:16:25 | 2024-09-07 17:16:27 |
Judging History
answer
#include <bits/stdc++.h>
#define D(...) fprintf(stderr,__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=1000005,K=20,P=1e9+7;
int n,W,p[N],w[N],f[N][K],lg[N],L[N],R[N];
int qmax(int l,int r){
int x=lg[r-l+1];
return max(f[l][x],f[r-(1<<x)+1][x]);
}
int tr[N];
void add(int x,int y){for(int i=x;i<N;i+=i&-i)tr[i]+=y;}
int query(int x){int y=0;for(int i=x;i;i&=i-1)y+=tr[i];return y;}
int cnt[N],pre[N],rev[N];
vector<int>vec[N];
struct cmp{
bool operator()(const int&x,const int&y)const{
return rev[x]>rev[y];
}
};
signed main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
rep(i,2,N-1)lg[i]=lg[i>>1]+1;
cin>>n>>W;
rep(i,1,n)cin>>p[i];
for(int i=1;i<=n;i++) rev[p[i]]=i;
rep(i,1,n)cin>>w[p[i]];
rep(i,1,n)f[i][0]=w[i];
rep(j,1,K-1)rep(i,1,n-(1<<j)+1)f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
rep(i,1,n){
L[i]=R[i]=i;
per(j,K-1,0)if(L[i]-(1<<j)>=1&&qmax(L[i]-(1<<j),i)<=W-w[i])L[i]-=1<<j;
per(j,K-1,0)if(R[i]+(1<<j)<=n&&qmax(i,R[i]+(1<<j))<=W-w[i])R[i]+=1<<j;
}
vector<int>id;
int lst=0;
rep(i,1,n)if(w[i]>W/2)add(i,1),cnt[lst]++,pre[i]=lst,lst=i;else id.pb(i);
sort(id.begin(),id.end(),[&](int lhs,int rhs){return R[lhs]-L[lhs]<R[rhs]-L[rhs];});
int ans=1;
rep(_,0,SZ(id)-1){
int i=id[_];
int x=query(R[i])-query(L[i]-1);
// D("i=%d l=%d r=%d x=%d\n",i,L[i],R[i],x);
ans=1LL*ans*(x+1)%P;
add(L[i],1);
}
printf("%d\n",ans);
for(auto&i:id)vec[R[i]+1].pb(i);
for(int i:id) cnt[L[i]-1]++;
priority_queue<int,vector<int>,cmp>pq;
for(auto&x:vec[n+1]){
pq.push(x);
}
if(lst>0&&cnt[lst]==0) pq.push(lst);
while(!pq.empty()){
int u=pq.top();
printf("%d ",pq.top());
pq.pop();
int p=w[u]>W/2?pre[u]:L[u]-1;
cnt[p]--;
if(p>=1&&cnt[p]==0) pq.push(p);
if(w[u]>W/2) for(int i:vec[u]) pq.push(i);
/*
if(pos&&pq.top()==p[pos]){
for(auto&x:vec[pos])pq.push(p[x]);
--pos;
while(pos&&w[pos]<=W/2)--pos;
if(pos)pq.push(p[pos]);
}
*/
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 27248kb
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: 0ms
memory: 26564kb
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: 0ms
memory: 23548kb
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: 5ms
memory: 27804kb
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: -100
Wrong Answer
time: 48ms
memory: 34068kb
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 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...
result:
wrong answer 2nd lines differ - expected: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 99996 99997 99998 99999 100000', found: '1996 78922 45321 68844 32404 8... 35601 78797 75927 58602 42513 '