Submission #43530

#	Time	Username	Problem	Language	Result	Execution time	Memory
43530		nonocut	Teams (IOI15_teams)	C++14	100 / 100	3916 ms	379576 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second

const int maxn = 5e5 + 5;

struct node {
    int val;
    node *l, *r;
};

int n,m;
vector<int> p[maxn];
node* root[maxn];

pii q[maxn];
int used[maxn];

node* getnode() {
    node* temp = new node;
    temp->val = 0; temp->l = temp->r = nullptr;
    return temp;
}

void build(node *pos, int l, int r) {
    if(l==r) return ;
    int mid = (l+r)/2;
    pos->l = getnode(); pos->r = getnode();
    build(pos->l, l, mid); build(pos->r, mid+1, r);
    pos->val = pos->l->val + pos->r->val;
}

void upgrade(node *last, node *pos, int l, int r, int x) {
    if(l==r) {
        pos->val = last->val + 1;
        return ;
    }
    int mid = (l+r)/2;
    if(x<=mid) {
        pos->l = getnode();
        pos->r = last->r;
        upgrade(last->l, pos->l, l, mid, x);
    }
    else {
        pos->l = last->l;
        pos->r = getnode();
        upgrade(last->r, pos->r, mid+1, r, x);
    }
    pos->val = pos->l->val + pos->r->val;
}

int query(node *pos, int l, int r, int x, int y) {
    if(r<x || y<l) return 0;
    if(x<=l && r<=y) return pos->val;
    int mid = (l+r)/2;
    return query(pos->l,l,mid,x,y) + query(pos->r,mid+1,r,x,y);
}

void init(int N, int A[], int B[]) {
    n = N;
    for(int i=0;i<n;i++) p[A[i]].push_back(B[i]);
    root[0] = getnode();
    build(root[0],1,n);
    for(int i=1;i<=n;i++) {
        root[i] = root[i-1];
        for(auto x : p[i]) {
            node *temp = getnode();
            upgrade(root[i],temp,1,n,x);
            root[i] = temp;
        }
    }
}

int can(int M, int K[]) {
    int sum = 0;
    for(int i=0;i<M;i++) sum += K[i];
    if(sum>n) return 0;
    sort(K, K+M); m = 0;
    for(int i=0;i<M;i++) {
        if(i==0 || K[i]!=K[i-1]) q[++m] = {K[i], 0};
        q[m].Y += K[i];
    }
    q[m+1].X = n+1;
    for(int i=1;i<=m;i++) used[i] = 0;
    for(int i=1;i<=m;i++) {
        int want = q[i].Y;
//        printf("want %d : %d\n",i,want);
        for(int j=i;j<=m;j++) {
            int have = query(root[q[i].X],1,n,q[j].X,q[j+1].X-1) - used[j];
            used[j] += min(want, have);
            want -= min(want, have);
            if(want==0) break;
//            printf("----- have [%d, %d] => [%d, %d] : %d - %d\n",1,q[i].X,q[j].X,q[j+1].X-1,have+used[j],used[j]);
        }
        if(want>0) return 0;
    }
    return 1;
}

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