QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#686889 | #5417. Chat Program | wangxiaorui# | WA | 1ms | 4012kb | C++14 | 1.5kb | 2024-10-29 16:16:48 | 2024-10-29 16:16:49 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200010;
int n,a[N],m,k,c,d;
ll p[N],sum[N];
ll b[N*3],idx;
ll tr[N*3];
unordered_map <ll,int> mp;
int lowbit(int x){
return x&(-x);
}
void add(int x,int v){
for(;x<=idx;x+=lowbit(x)) tr[x]+=v;
}
int query(int x){
int res=0;
for(;x;x-=lowbit(x)) res+=tr[x];
return res;
}
bool check(ll mid){
// cout<<mid<<endl;
for(int i=1;i<=idx;i++) tr[i]=0;
mp.clear();idx=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1];
if(mid<=a[i]){
sum[i]=sum[i-1]+1;
p[i]=0;
}
else{
p[i]=mid-a[i];
if(p[i]<=c) p[i]=1;
else{
if(!d){
p[i]=1e16;
}
else{
if((p[i]-c)%d==0) p[i]=1+(p[i]-c)/d;
else p[i]=1+(p[i]-c)/d+1;
}
}
}
b[++idx]=p[i]-i;b[++idx]=m-i;
}
sort(b+1,b+1+idx);
idx=unique(b+1,b+1+idx)-b-1;
int t;
for(int i=1;i<=idx;i++) mp[b[i]]=i;
for(int i=1;i<=n;i++){
add(mp[p[i]-i],1);
if(i>=m){
t=query(mp[m-i])-(sum[i]-sum[i-m]);
if(t+sum[n]>=k) return 1;
add(mp[i-m+1-(i-m+1)],-1);
}
}
return 0;
}
void solve(){
cin>>n>>k>>m>>c>>d;
for(int i=1;i<=n;i++) cin>>a[i];
ll l=0,r=1e15,mid,res=-1;
while(l<=r){
mid=(l+r)>>1;
if(n>=200010) cout<<l<<' '<<r<<' '<<mid<<endl;
if(!check(mid)) r=mid-1;
else l=mid+1,res=mid;
}
cout<<res<<endl;
}
int main()
{
freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4012kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
-1
result:
wrong answer 1st numbers differ - expected: '4', found: '-1'