QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#425786 | #7279. Tricks of the Trade | Lynkcat# | 0 | 0ms | 22100kb | C++20 | 5.4kb | 2024-05-30 16:57:33 | 2024-05-30 16:57:34 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
#define int ll
// #define N
using namespace std;
const int N=250005;
int cnt;
struct node
{
int x,y,ls,rs;
}tr[N*64];
int n,K;
int m;
int a[N],b[N],v[N][3];
int pos[N];
int rt[N];
poly g;
poly I[N],E[N];
int vis[N];
int from[N],from1[N];
int update(int u,int l,int r,int L,int x,int y)
{
int k=++cnt;
tr[k]=tr[u];
tr[k].x+=x;
tr[k].y+=y;
if (l==r) return k;
int mid=l+(r-l)/2;
if (L<=mid) tr[k].ls=update(tr[u].ls,l,mid,L,x,y);
else tr[k].rs=update(tr[u].rs,mid+1,r,L,x,y);
return k;
}
int Mn,Sum;
void qry(int kr,int kl,int l,int r,int k)
{
if (l==r)
{
Mn=l;
Sum+=k*g[l-1];
return;
}
int mid=l+(r-l)/2;
int rt=tr[tr[kr].rs].x-tr[tr[kl].rs].x;
if (k>rt)
{
Sum+=tr[tr[kr].rs].y-tr[tr[kl].rs].y;
qry(tr[kr].ls,tr[kl].ls,l,mid,k-rt);
} else
{
qry(tr[kr].rs,tr[kl].rs,mid+1,r,k);
}
}
int trans(int i,int j)
{
if (j-i-1>=K-2)
{
Mn=sz(g)+1,Sum=0;
if (K-2)
qry(rt[j-1],rt[i],1,m,K-2);
Mn--;
if (Mn<sz(g)) Mn=g[Mn]; else Mn=inf;
return Sum+v[j][2]+v[i][0];
}
return -inf;
}
void solve(int l,int r,int L,int R)
{
if (l==r)
{
for (int i=L;i<=R;i++) from[i]=l;
return;
}
if (L>R) return;
int mid=L+(R-L)/2;
int pos=l,lstv=trans(l,mid);
for (int i=l;i<mid&mid-i-1>=K-2&&i<=r;i++)
{
int nv=trans(i,mid);
if (nv>=lstv)
{
pos=i;
lstv=nv;
}
}
from[mid]=pos;
solve(l,pos,L,mid-1);
solve(pos,r,mid+1,R);
}
void solve1(int l,int r,int L,int R)
{
if (l==r)
{
for (int i=L;i<=R;i++) from1[i]=l;
return;
}
if (L>R) return;
int mid=L+(R-L)/2;
int pos=l,lstv=trans(l,mid);
for (int i=l;i<mid&mid-i-1>=K-2&&i<=r;i++)
{
int nv=trans(i,mid);
if (nv>lstv)
{
pos=i;
lstv=nv;
}
}
from1[mid]=pos;
solve1(l,pos,L,mid-1);
solve1(pos,r,mid+1,R);
}
int lst_oc[N],fst_oc[N];
void BellaKira()
{
cin>>n>>K;
for (int i=1;i<=n;i++)
cin>>a[i],a[i]+=a[i-1];
for (int i=1;i<=n;i++)
cin>>b[i];
for (int i=1;i<=n;i++)
{
v[i][0]=b[i]+a[i-1];
v[i][1]=b[i];
v[i][2]=b[i]-a[i];
}
if (K==1)
{
int mn=inf;
for (int i=1;i<=n;i++) mn=min(mn,b[i]-a[i]+a[i-1]);
cout<<mn<<'\n';
for (int i=1;i<=n;i++)
if (b[i]-a[i]+a[i-1]==mn) cout<<1;
else cout<<0;
cout<<'\n';
return;
}
for (int i=1;i<=n;i++)
{
g.push_back(v[i][1]);
}
sort(g.begin(),g.end());
g.erase(unique(g.begin(),g.end()),g.end());
for (int i=1;i<=n;i++)
{
pos[i]=lower_bound(g.begin(),g.end(),v[i][1])-g.begin()+1;
}
m=sz(g);
for (int i=1;i<=n;i++)
{
rt[i]=rt[i-1];
rt[i]=update(rt[i],1,m,pos[i],1,v[i][1]);
}
int ans=-inf;
int lst=1;
solve(1,n,2,n);
solve1(1,n,2,n);
map<int,int>mmp;
mmp[v[1][0]]=1;
fst_oc[1]=1;
for (int j=2;j<=n;j++)
{
lst_oc[j]=mmp[v[j][0]];
if (lst_oc[j]) fst_oc[j]=fst_oc[lst_oc[j]];
else fst_oc[j]=j;
mmp[v[j][0]]=j;
ans=max(ans,trans(from[j],j));
}
for (int j=2;j<=n;j++)
{
int i=from[j];
if (trans(i,j)==ans)
{
// cout<<from1[i]<<"..."<<i<<" "<<trans(i,j)<<" "<<trans(1,j)<<endl;
E[from1[i]].push_back(j),I[i].push_back(j),vis[i]|=2,vis[j]|=1;
}
}
for (int i=n;i>=1;i--) vis[lst_oc[i]]|=vis[i]&2;
multiset<int>S;
if (K-2)
{
for (int i=n;i>=1;i--)
{
for (auto u:I[i]) S.insert(u);
for (auto u:E[i]) S.erase(S.find(u));
poly().swap(I[i]);
poly().swap(E[i]);
if (S.size())
{
int j=(*S.begin());
// cout<<"?"<<i<<" "<<j<<endl;
if (j-i<=K-2) vis[i]=1;
else
{
Mn=sz(g)+1,Sum=0;
qry(rt[j-1],rt[i-1],1,m,K-2);
Mn--;
if (Mn<sz(g)) Mn=g[Mn]; else Mn=inf;
if (Mn<=v[i][1]) vis[i]|=1;
}
}
}
}
for (int j=2;j<=n;j++)
{
int i=from[j];
if (trans(i,j)==ans)
{
I[i].push_back(Mn),E[j].push_back(Mn),vis[i]|=2,vis[j]|=1;
}
}
for (int i=1;i<=n;i++)
{
for (auto u:I[i]) S.insert(u);
for (auto u:E[i]) S.erase(S.find(u));
if (S.size()&&v[i][1]>=(*S.begin())) vis[i]|=1;
}
cout<<ans<<'\n';
for (int i=1;i<=n;i++) cout<<(vis[i]>0);
cout<<'\n';
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
while (T--)
{
BellaKira();
}
}
/*list:
1.mod 998244353 or 1e9+7 or ???
2.N
3.duipai shuju xingtai duoyidian
...
*/
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 10
Accepted
time: 0ms
memory: 22012kb
input:
5 3 3 5 2 3 6 2 1 5 2 3
output:
-1 00111
result:
ok all correct
Test #2:
score: 5
Acceptable Answer
time: 0ms
memory: 22100kb
input:
200 40 81 50 87 91 54 1 77 68 19 84 28 81 45 64 4 13 25 89 12808135 86 40 73 47 18 82 79 11 96 16 34 80 36 8 5 60 76 86 84 36 37 96 55 68 12807879 51 89 57 30 100 11 44 19 96 32 9 68 41 12808009 5 58 12807939 92 68 67 78 32 57 49 71 92 64 35 89 76 81 36 6 6 53 31 85 79 5 85 1 91 17 37 25 91 54 29 47...
output:
12807909 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111011100111110111111111100111111111111111111111111111111111111111111111111000000000000000000000000000000000000
result:
points 0.50 first question correct
Test #3:
score: 5
Acceptable Answer
time: 0ms
memory: 22088kb
input:
200 41 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
81 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000
result:
points 0.50 first question correct
Test #4:
score: 0
Runtime Error
input:
5 2 1 6 1 5 2 4 1 6 2 4
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Runtime Error
Test #30:
score: 0
Runtime Error
input:
5 2 1 6 1 5 2 4 1 6 2 4
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%