Submission #1009934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009934		hotboy2703	Teams (IOI15_teams)	C++17	0 / 100	653 ms	524288 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 l1,ll r1,ll val){
    if (l > r1 || l1 > r)return cur;
    if (l1 <= l && r <= r1){
        node* res = new node;
        res->lazy=cur->lazy+val;
        res->l=cur->l;
        res->r=cur->r;
        return res;
    }
    ll mid = (l + r) >> 1;
    node *res = new node;
    res->lazy=cur->lazy;
    res->l = update(cur->l,l,mid,l1,r1,val);
    res->r = update(cur->r,mid+1,r,l1,r1,val);
    return res;
}
node* update(node* cur,ll l,ll r,ll val){
    return update(cur,0,MAXM,l,r,val);
}
ll get(node* cur,ll l,ll r,ll i,ll val){
    if (l==r){
        return val + cur->lazy;
    }
    ll mid = (l + r) >> 1;
    val += cur->lazy;
    if (mid >= i)return get(cur->l,l,mid,i,val);
    return get(cur->r,mid+1,r,i,val);
}
ll get(node* cur,ll i){
    return get(cur,0,MAXM,i,0);
}

node *tree[MAXM+100];
ll query(ll l,ll r){
    return get(tree[r],l);
}
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]-1});
        a.push_back({A[i]-1,A[i]-1});
    }
    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],0,a[ptr].se,a[ptr].fi==a[ptr].se?-1:+1);
            ptr++;
        }
//        if (i <= 3){
//            for (ll j = 0;j <= 3;j ++){
//                cout<<get(tree[i],j)<<' ';
//            }
//            cout<<'\n';
//        }
    }
}
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;
        if (cur < sum)return 0;
        for (ll j = i + 1;j < sz(c);j ++){
            cur += pre[i];
            sum += c[j].fi * c[j].se;
            if (cur < sum)return 0;
        }
    }
	return 1;
}

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