QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425786#7279. Tricks of the TradeLynkcat#0 0ms22100kbC++205.4kb2024-05-30 16:57:332024-05-30 16:57:34

Judging History

你现在查看的是最新测评结果

  • [2024-05-30 16:57:34]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:22100kb
  • [2024-05-30 16:57:33]
  • 提交

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%