Submission #1211021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211021		12345678	Teams (IOI15_teams)	C++17	13 / 100	1487 ms	379380 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, dp[nx], pos[nx], need[nx];
vector<int> cmp[nx];

struct persist
{
    struct node
    {
        int f;
        node *l, *r;
        node(): f(0), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &k)
    {
        k=new node();
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, k->l);
        build(md+1, r, k->r);
    }
    void update(int l, int r, pnode &k, pnode p, int idx)
    {
        k=new node(*p);
        if (l==r) return k->f++, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, p->l, idx);
        else update(md+1, r, k->r, p->r, idx);
        k->f=k->l->f+k->r->f;
    }
    int query(int l, int r, pnode k, pnode p, int idx)
    {
        if (r<idx) return 0;
        if (idx<=l) return k->f-p->f;
        int md=(l+r)/2;
        return query(l, md, k->l, p->l, idx)+query(md+1, r, k->r, p->r, idx);
    }
} s;

void init(int N, int A[], int B[]) {
	n=N;
    for (int i=0;i <n; i++) cmp[A[i]].push_back(B[i]);
    s.build(1, n, s.rt[0]);
    for (int i=1; i<=n; i++)
    {
        s.rt[i]=s.rt[i-1];
        for (auto x:cmp[i]) s.update(1,n , s.rt[i], s.rt[i], x);
    }
}

struct range
{
    int l, r, p;
    range(int l=0, int r=0, int p=0): l(l), r(r), p(p){}
};

int cost(int pv, int x)
{
    return dp[pv]+s.query(1, n, s.rt[x], s.rt[pos[pv]], x);
}

int can(int M, int K[]) {
    map<int, int> mp;
    int sm=0, t=0;
    for (int i=0; i<M; i++) 
    {
        sm+=K[i];
        mp[K[i]]+=K[i];
        if (sm>n) return 0;
    }
    int sz=mp.size(), mn=0;
    for (int i=1; i<=sz; i++) dp[i]=INT_MAX;
    for (auto &[x, y]:mp) t++, pos[t]=x, need[t]=y;
    deque<range> dq;
    dq.push_back(range(1, n, 0));
    for (int i=1; i<=sz; i++)
    {
        dp[i]=min(dp[i], cost(dq.front().p, pos[i])-need[i]);
        //for (auto x:dq) cout<<"dq "<<x.l<<' '<<x.r<<' '<<x.p<<'\n';
        //cout<<"debug "<<i<<' '<<dp[i]<<'\n';
        if (dq.front().r==pos[i]) dq.pop_front();
        else dq.front().l++;
        while (!dq.empty()&&cost(dq.front().p, dq.front().r)>=cost(i, dq.front().r)) dq.pop_front();
        if (dq.empty()) dq.push_back(range(pos[i]+1, n, i));
        else
        {
            int l=dq.front().l, r=dq.front().r;
            while (l<r)
            {
                int md=(l+r)/2;
                if (cost(dq.front().p, md)<cost(i, md)) r=md;
                else l=md+1;
            }
            dq.front().l=l;
            if (dq.front().l!=pos[i]+1) dq.push_front(range(pos[i]+1, dq.front().l-1, i));
        }
        mn=min(mn, dp[i]);
    }
	return mn>=0;
}

• Subtask 1: 0 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23