Submission #1211018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211018		12345678	Teams (IOI15_teams)	C++17	77 / 100	4072 ms	373248 KiB

teams

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

using namespace std;

const int nx=5e5+5;

int n;
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;
        //cout<<"seg "<<k->f<<'\n';
    }
    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);
    }
}

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;
    vector<int> dp(sz+1, INT_MAX), pos(sz+1), need(sz+1);
    for (auto &[x, y]:mp) t++, pos[t]=x, need[t]=y;
    dp[0]=0;
    for (int i=1; i<=sz; i++)
    {
        for (int j=0; j<i; j++) dp[i]=min(dp[i], dp[j]+s.query(1, n, s.rt[pos[i]], s.rt[pos[j]], pos[i])-need[i]);
        //cout<<"debug "<<i<<' '<<dp[i]<<'\n';
        //cout<<"need "<<need[i]<<' '<<pos[i]<<' '<<s.query(1, n, s.rt[pos[i]], s.rt[0], pos[i])<<'\n';
        mn=min(mn, dp[i]);
    }
	return mn>=0;
}

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