QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672300 | #5417. Chat Program | Yurily | WA | 2266ms | 19284kb | C++20 | 2.5kb | 2024-10-24 16:21:39 | 2024-10-24 16:21:40 |
Judging History
answer
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+5;
int n,k,m;
long long c,d;
long long a[MAX],tmp[MAX];
int ori[MAX],tot_ori;
set<long long> s;
long long g[MAX];
int tot;
int sum[MAX];
int findf(long long x){
int l=1,r=tot,res=-1;
while(l<=r){
int mid=l+r>>1;
if(g[mid]>=x){
res=mid;
r=mid-1;
}
else
l=mid+1;
}
return res;
}
int lowbit(int x){
return x&(-x);
}
void modify(int p,int v){
while(p<=tot){
sum[p]+=v;
p+=lowbit(p);
}
}
int query(int p){
int res=0;
while(p){
res+=sum[p];
p-=lowbit(p);
}
return res;
}
int check(long long x){
memset(sum,0,sizeof(sum));
int res=0;
tot_ori=0;
for(int i=1;i<=n;++i){
if(a[i]>=x)
tot_ori++;
}
ori[1]=0;
for(int i=1;i<=m;++i){
if(a[i]>=x)
ori[1]++;
}
for(int i=2;i+m-1<=n;++i){
ori[i]=ori[i-1];
if(a[i-1]>=x)
ori[i]--;
if(a[i+m-1]>=x)
ori[i]++;
// cout<<"(("<<i<<" "<<ori[i]<<endl;
}
// cout<<tot_ori<<endl;
res=tot_ori;
x-=c;
for(int i=n-m+1;i<=n;++i){
int p=findf(tmp[i]);
modify(p,1);
}
int p=findf(x);
if(p!=-1)
res=max(res,query(tot)-query(p-1)+tot_ori-ori[n-m+1]);
for(int i=n-m;i>=1;--i){
x-=d;
int p=findf(tmp[i+m]);
modify(p,-1);
p=findf(tmp[i]);
// cout<<"&"<<g[p]<<endl;
modify(p,1);
p=findf(x);
// cout<<"@"<<g[p]<<endl;
if(p!=-1)
res=max(res,query(tot)-query(p-1)+tot_ori-ori[i]);
// cout<<i<<" * "<<query(1,1,tot,p,tot)+tot_ori-ori[i]<<" "<<ori[i]<<endl;
}
// cout<<res<<"*"<<endl;
return res>=k;
}
int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-'){
f = -1;
}
c = getchar();
}
while(c >= '0' && c <= '9'){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
cin>>n>>k>>m>>c>>d;
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=n;++i)
tmp[i]=a[i];
int cur=0;
for(int i=1;i<=m;++i){
tmp[n-m+i]+=cur;
cur+=d;
}
cur=0;
for(int i=n-m+1;i>=1;--i){
tmp[i]+=cur;
cur-=d;
}
for(int i=1;i<=n;++i){
s.insert(tmp[i]);
}
for(set<long long>::iterator i=s.begin();i!=s.end();++i)
g[++tot]=*i;
long long l=0,r=2e15,res;
// check(9);
while(l<=r){
long long mid=l+r>>1;
// cout<<mid<<endl;
if(check(mid)){
res=mid;
l=mid+1;
}
else
r=mid-1;
}
cout<<res;
return 0;
}
//100001000000000
//100004147436544
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8084kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 2ms
memory: 8440kb
input:
7 3 2 4 0 1 9 1 9 8 1 0
output:
9
result:
ok 1 number(s): "9"
Test #3:
score: 0
Accepted
time: 1ms
memory: 8068kb
input:
8 3 5 0 0 2 0 2 2 1 2 1 8
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 2252ms
memory: 19228kb
input:
200000 200000 100000 0 1000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: -100
Wrong Answer
time: 2266ms
memory: 19284kb
input:
200000 1 100000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000000...
output:
100004147436544
result:
wrong answer 1st numbers differ - expected: '100001000000000', found: '100004147436544'