Submission #1010148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010148		hotboy2703	Teams (IOI15_teams)	C++17	100 / 100	1117 ms	366004 KiB

teams

#include "teams.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXM = 5e5;
struct node{
    node *l,*r;
    ll lazy;
};
void build(node *cur,ll l,ll r){
    cur->lazy=0;
    if (l!=r){
        ll mid = (l + r) >> 1;
        cur->l=new node;
        cur->r=new node;
        build(cur->l,l,mid);
        build(cur->r,mid+1,r);
    }
}
node* update(node* cur,ll l,ll r,ll i){
    if (l > i || r < i)return cur;
    if (l == r){
        node* res = new node;
        res->lazy=cur->lazy+1;
        res->l=cur->l;
        res->r=cur->r;
        return res;
    }
    ll mid = (l + r) >> 1;
    node *res = new node;
    res->l = update(cur->l,l,mid,i);
    res->r = update(cur->r,mid+1,r,i);
    res->lazy=res->l->lazy+res->r->lazy;
    return res;
}
node* update(node* cur,ll i){
//    cout<<"UPDATE "<<l<<' '<<r<<' '<<val<<endl;
    return update(cur,0,MAXM,i);
}
ll get(node* cur,ll l,ll r,ll l1,ll r1){
    if (l > r1 || l1 > r || l1 > r1)return 0;
    if (l1 <= l && r <= r1)return cur->lazy;
    ll mid = (l + r) >> 1;
    return get(cur->l,l,mid,l1,r1)+get(cur->r,mid+1,r,l1,r1);
}
ll get(node* cur,ll l,ll r){
    return get(cur,0,MAXM,l,r);
}

node *tree[MAXM+100];
ll query(ll l,ll r){
    return get(tree[r],l+1,r);
}
vector <pll> a;
ll n;
void init(int N, int A[], int B[]) {
    n=N;
    for (ll i = 0;i < n;i ++){
        a.push_back({B[i],A[i]});
    }
    sort(a.begin(),a.end(),greater <> ());
    tree[MAXM+1]=new node;
    build(tree[MAXM+1],0,MAXM);
    for (ll i = MAXM,ptr = 0;i >= 1;i --){
        tree[i] = tree[i+1];
        while (ptr < sz(a) && a[ptr].fi >= i){
            tree[i] = update(tree[i],a[ptr].se);
            ptr++;
        }
    }
}
ll b[MAXM+100];
ll m;
int can(int M, int K[]) {
//    if (n > 100000)return 0;
    m=M;
    ll sum = 0;
    for (ll i = 0;i < m;i ++){b[i] = K[i];sum += b[i];}
    if (sum > n)return 0;
    sort(b,b+m);
    vector <pll> c;
    for (ll i =0 ;i < m;i ++){
        if (sz(c)!=0&&c.back().fi==b[i]){
            c.back().se++;
        }
        else{
            c.push_back(MP(b[i],1));
        }
    }
    vector <ll> dp(sz(c));
    set <ll> s;
    set <pll> del;
    for (ll i = 0;i < sz(c);i ++){
        auto add_del=[&](set <ll> :: iterator tmp)->void{
            if (tmp==s.begin())return;
            ll x = *(prev(tmp));
            ll l = i;
            ll r = sz(c)-1;
            while (l <= r){
                ll mid = (l + r) >> 1;
                if (dp[x] - query(c[x].fi,c[mid].fi) > dp[*tmp] - query(c[*tmp].fi,c[mid].fi)){
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            del.insert(MP(l,*tmp));
        };
        if (i){
            auto tmp = s.insert(i-1);
            add_del(tmp.fi);
        }
        while (sz(del) && (*(del.begin())).fi == i){
            auto x = s.find((*(del.begin())).se);
            del.erase(del.begin());
            if (x==s.end())continue;
            auto tmp=s.erase(x);

            if (tmp!=s.end()){
                add_del(tmp);
            }
        }
        dp[i] = c[i].fi*c[i].se-query(0,c[i].fi);
        if (sz(s)){
            ll j = *(s.rbegin());
            dp[i] = max(dp[i],dp[j] + c[i].fi*c[i].se-query(c[j].fi,c[i].fi));
        }
        if (dp[i] > 0)return 0;
    }
	return 1;
}

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