QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#292722 | #7417. Honorable Mention | DaiRuiChen007 | TL | 3ms | 16972kb | C++17 | 2.2kb | 2023-12-28 11:58:34 | 2023-12-28 11:58:34 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define sz(v) int(v.size())
using namespace std;
const int MAXN=35005;
const ll inf=1e12;
typedef vector<ll> poly;
poly operator *(poly f,poly g) {
if(f.empty()||g.empty()) return {};
poly h(sz(f)+sz(g)-1);
int i=1,j=1,k=1; h[0]=f[0]+g[0];
while(i<sz(f)&&j<sz(g)) {
if(f[i]-f[i-1]>g[j]-g[j-1]) h[k]=h[k-1]+f[i]-f[i-1],++i,++k;
else h[k]=h[k-1]+g[j]-g[j-1],++j,++k;
}
while(i<sz(f)) h[k]=h[k-1]+f[i]-f[i-1],++i,++k;
while(j<sz(g)) h[k]=h[k-1]+g[j]-g[j-1],++j,++k;
return h;
}
int n,q,a[MAXN];
poly tr[MAXN<<2][2][2];
void build(int l=1,int r=n,int p=1) {
if(l==r) {
tr[p][0][0]={0,a[l]},tr[p][0][1]=tr[p][1][0]=tr[p][1][1]={-inf,a[l]};
return ;
}
int mid=(l+r)>>1;
build(l,mid,p<<1),build(mid+1,r,p<<1|1);
for(int i:{0,1}) for(int j:{0,1}) {
poly x=tr[p<<1][i][0]*tr[p<<1|1][0][j];
poly y=tr[p<<1][i][1]*tr[p<<1|1][1][j];
tr[p][i][j].resize(r-l+2);
for(int k=0;k+1<sz(y);++k) tr[p][i][j][k]=max(x[k],y[k+1]);
tr[p][i][j][r-l+1]=x[r-l+1];
}
}
struct info {
ll v; int c;
friend info operator +(info x,info y) { return {x.v+y.v,x.c+y.c}; }
friend bool operator <(info x,info y) { return x.v==y.v?x.c<y.c:x.v<y.v; }
};
typedef array<array<info,2>,2> mat;
info eval(poly &f,ll d) {
int l=1,r=sz(f)-1,p=0;
while(l<=r) {
int mid=(l+r)>>1;
if(f[mid]-f[mid-1]>=d) l=mid+1,p=mid;
else r=mid-1;
}
return {f[p]-d*p,p};
}
mat qry(int ul,int ur,ll d,int l=1,int r=n,int p=1) {
if(ul<=l&&r<=ur) {
mat f;
for(int i:{0,1}) for(int j:{0,1}) f[i][j]=eval(tr[p][i][j],d);
return f;
}
int mid=(l+r)>>1;
if(ur<=mid) return qry(ul,ur,d,l,mid,p<<1);
if(mid<ul) return qry(ul,ur,d,mid+1,p<<1|1);
mat f=qry(ul,ur,d,l,mid,p<<1),g=qry(ul,ur,d,mid+1,p<<1|1),h;
for(int i:{0,1}) for(int j:{0,1}) {
h[i][j]=min(f[i][0]+g[0][j],f[i][1]+g[1][j]+info{d,-1});
}
return h;
}
signed main() {
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
for(int l,r,k;q--;) {
scanf("%d%d%d",&l,&r,&k);
ll L=-inf,R=inf,d=R;
while(L<=R) {
ll mid=(L+R)>>1;
if(qry(l,r,mid)[0][0].c<=k) R=mid-1,d=mid;
else L=mid+1;
}
printf("%lld\n",qry(l,r,d)[0][0].v+k*d);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 16896kb
input:
5 5 -1 2 -3 4 -5 1 5 1 1 5 2 1 5 3 1 5 4 1 5 5
output:
4 6 5 2 -3
result:
ok 5 number(s): "4 6 5 2 -3"
Test #2:
score: 0
Accepted
time: 3ms
memory: 16972kb
input:
5 1 7 7 7 7 7 1 5 1
output:
35
result:
ok 1 number(s): "35"
Test #3:
score: -100
Time Limit Exceeded
input:
25000 25000 -11889 -16468 18402 -13238 14125 12120 -3295 -12106 20152 7478 8575 9968 -13946 -13408 23715 -14670 -21837 12589 7029 20609 2868 12728 -6942 982 5884 -7561 -2058 -7892 7806 16344 14645 13904 7355 9860 15446 -539 24072 21969 19028 -24939 -21911 -11836 21045 -4727 -3882 2138 18513 -4796 -1...