Submission #1010113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010113		hotboy2703	Teams (IOI15_teams)	C++17	77 / 100	938 ms	366676 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));
    vector <ll> cvh;
    for (ll i = 0;i < sz(c);i ++){
        if (i){
            while (sz(cvh) && dp[cvh.back()] - query(c[cvh.back()].fi,c[i].fi) <= dp[i-1] - query(c[i-1].fi,c[i].fi))cvh.pop_back();
            cvh.push_back(i-1);
        }
        dp[i] = c[i].fi*c[i].se-query(0,c[i].fi);
        if (sz(cvh)){ll j = cvh[0];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: 0 / 23