QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #551506 | #9252. Penguins in Refrigerator | ucup-team052# | WA | 47ms | 32472kb | C++23 | 2.2kb | 2024-09-07 17:08:53 | 2024-09-07 17:08:54 |
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(p[x]);
}
if(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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 27412kb
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: 27484kb
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: 23256kb
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: 25112kb
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: 47ms
memory: 32472kb
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 '