QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #551565 | #9252. Penguins in Refrigerator | ucup-team052# | WA | 48ms | 36036kb | C++23 | 2.2kb | 2024-09-07 17:21:38 | 2024-09-07 17:21:38 |
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 p[x]>p[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[rev[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: 6ms
memory: 27388kb
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: 27964kb
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: 22580kb
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: 2ms
memory: 27676kb
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: 36036kb
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 90351 26042 37191 67363 93481 31857 75572 63581 71021 67964 99563 87893 17623 55524 67542 91441 83207 81850 88998 52754 88210 59523 28206 10773 2419 88793 49662 41825 48592 49228 24066 50046 6231 3603 22544 62993 17815 8312 98325 18532 21466 37790 90408 39273 26825 79488 25009 6232 75004 7...
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: '90351 26042 37191 67363 93481 ... 17445 23970 74516 73080 54268 '