제출 #1142988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142988		idiotcomputer	Teams (IOI15_teams)	C++20	100 / 100	1175 ms	520224 KiB

teams

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second 
#define sz(x) (int) (x).size()
#define pb push_back
#include "teams.h"
const int mxN = 5e5+5;
int n;

using sn = struct node*;
struct node {
    sn c[2] = {nullptr, nullptr};
    int v,l,r;
    node(sn c1, sn c2, int tv, int tl, int tr){
        c[0] = c1;
        c[1] = c2;
        v = tv;
        l = tl;
        r = tr;
    }
};

sn roots[mxN];

sn upd(sn c, int t, int v){
    if (c->l > t || c->r < t) return c;
    sn temp = new node(c->c[0],c->c[1],c->v,c->l,c->r);
    temp->v++;
    if (c->l == c->r) return temp;
    int m = (c->l + c->r)/2;
    if (m >= t){
        if (temp->c[0] == nullptr) temp->c[0] = new node(nullptr,nullptr,0,c->l,m);
        temp->c[0] = upd(temp->c[0],t,v);
    } else {
        if (temp->c[1] == nullptr) temp->c[1] = new node(nullptr,nullptr,0,m+1,c->r);
        temp->c[1] = upd(temp->c[1], t,v);
    }
    return temp;
}

int query(sn c, int t){
    if (c == nullptr) return 0;
    if (c->r < t) return 0;
    if (c->l >= t) return c->v;
    return query(c->c[0],t) + query(c->c[1],t);
}


int q2(sn c, sn c2, int v){
    int l1 = 0;
    int l2 = 0;
    int r1 = 0;
    int r2 = 0;
    if (c->c[0]) l1 = c->c[0]->v;
    if (c->c[1]) r1 = c->c[1]->v;
    if (c2->c[0]) l2 = c2->c[0]->v;
    if (c2->c[1]) r2 = c2->c[1]->v;
    if (c->v - c2->v <= v) return c->l;
    if (c->l == c->r) return c->r+1;

    int m = (c->l + c->r)/2;
    if (r1 - r2 >= v) {
        //go right side
        bool w1 = 0;
        bool w2 = 0;
        if (!c->c[1]) c->c[1] = new node(nullptr,nullptr,0,m+1,c->r), w1 = 1;
        if (!c2->c[1]) c2->c[1] = new node(nullptr, nullptr, 0,m+1,c->r), w2 = 1;
        int res = q2(c->c[1],c2->c[1],v);
        if (w1) delete c->c[1], c->c[1] = nullptr;
        if (w2) delete c2->c[1], c2->c[1] = nullptr;
        return res;
    } else {
        bool w1 = 0;
        bool w2 = 0;
        if (!c->c[0]) c->c[0] = new node(nullptr,nullptr,0,c->l,m), w1 = 1;
        if (!c2->c[0]) c2->c[0] = new node(nullptr, nullptr,0,c->l,m), w2 = 1;
        int res =  q2(c->c[0],c2->c[0],v-(r1-r2));
        if (w1) delete c->c[0], c->c[0] = nullptr;
        if (w2) delete c2->c[0], c2->c[0] = nullptr;
        return res;
    }
}

int bet(pii a, pii b){
    if (a.f > b.f) swap(a,b);
    // when a gets better than b
    //a + q(b,i) <= b
    //q(b,i) <= b-a
    int diff = b.s- a.s;
    return q2(roots[b.f],roots[a.f],diff);
}

vector<pii> all;

void init(int N, int A[], int B[]){
    n = N;
    for (int i = 0; i < mxN; i++) roots[i] = nullptr;
    all.resize(n);
    for (int i = 0; i < n; i++) all[i].f = A[i], all[i].s = B[i];
    sort(all.begin(),all.end());

    roots[0] = new node(nullptr,nullptr,0,0,n);
    int idx = 0;
    for (int i = 1; i <= n; i++){
        roots[i] = roots[i-1];
        while (idx < sz(all) && all[idx].f == i) roots[i] = upd(roots[i],all[idx].s,1), idx++;
    }

}

//Brute force for subtask 1
bool brute(int M, vector<int> &K){
    multiset<pii> cop;
    for (int i = 0; i < n; i++) cop.insert({all[i].s, all[i].f});
    int cnt;
    auto it = cop.begin();
    for (int i =0 ; i < M; i++){
        it = cop.begin();
        cnt = 0;
        while (it != cop.end() && cnt < K[i]){
            if (it->f < K[i] || it->s > K[i]){ it++; continue;}
            cnt++;
            it++;
            cop.erase(prev(it));
        }
        if (cnt < K[i]) return 0;
    }
    return 1;
}

int can(int M, int K[]){
    int m = M;
    vector<int> k(m);
    for (int i = 0; i < m; i++) k[i] = K[i];
    sort(k.begin(),k.end());

    int res = n+1;
    vector<pii> act;
    act.pb({0,0});
    for (int i = 0; i < m; i++){
        while (sz(act) > 1 && bet(act[sz(act)-2], act[sz(act)-1]) <= k[i]) act.pop_back();
        int cur = act.back().s + query(roots[k[i]], k[i]) - query(roots[act.back().f], k[i]) - k[i];
        pii temp = {k[i],cur};
        res = min(res, cur);
        while (sz(act) > 1 && bet(act[sz(act)-2], act[sz(act)-1]) <= bet(act[sz(act)-1], temp)) act.pop_back();
        act.pb(temp);
    }
    return (res>=0);
}

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