Submission #1009995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009995		hotboy2703	Teams (IOI15_teams)	C++17	0 / 100	508 ms	431292 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 = 2e5;
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)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;
void init(int n, int A[], int B[]) {
    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];
ll m;
int can(int M, int K[]) {
    m=M;
    for (ll i = 0;i < m;i ++)b[i] = K[i];
    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> pre(sz(c));
    for (ll i = 1;i < sz(c);i ++){
        pre[i] = query(c[i-1].fi,c[i].fi);
    }
    for (ll i = 0;i < sz(c);i ++){
        ll cur = query(0,c[i].fi);
        ll sum = c[i].fi*c[i].se;
//        cout<<i<<' '<<cur<<' '<<sum<<endl;
        if (cur < sum)return 0;
        for (ll j = i + 1;j < sz(c);j ++){
            cur += pre[j];
            sum += c[j].fi * c[j].se;
//            cout<<i<<' '<<j<<' '<<cur<<' '<<sum<<endl;
            if (cur < sum)return 0;
        }
    }
	return 1;
}

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