제출 #1142972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142972		idiotcomputer	팀들 (IOI15_teams)	C++20	77 / 100	865 ms	527748 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 ccc = 10;

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;

   /* if (ccc > 0 && c->r < 10){
        cout << c->l << "," << c->r << " " << l1 << ',' << r1 << " " << l2 << ',' << r2 << '\n';
        cout << v << '\n';
        ccc--;
    }*/
    int m = (c->l + c->r)/2;
    if (r1 - r2 >= v) {
        //go right side
        if (!c->c[1]) c->c[1] = new node(nullptr,nullptr,0,m+1,c->r);
        if (!c2->c[1]) c2->c[1] = new node(nullptr, nullptr, 0,m+1,c->r);
        return q2(c->c[1],c2->c[1],v); 
    } else {
        if (!c->c[0]) c->c[0] = new node(nullptr,nullptr,0,c->l,m);
        if (!c2->c[0]) c2->c[0] = new node(nullptr, nullptr,0,c->l,m);
        return q2(c->c[0], c2->c[0], v-(r1-r2));
    }
}

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++;
    }

 //   for (pii c : all) cout << c.f << "," << c.s << " ";
 //   cout << '\n';
   //     cout << query(roots[1],3) << '\n';

}

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});
   // for (pii c :cop) cout << c.f << "," << c.s <<"\n";
   // for (int c : K) cout << c << " ";
   // cout << '\n';
    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));
        }
      //  cout << i << " " << cnt << '\n';
     //   if (cnt < K[i]) cout << "DOESNT WROK " << i << " " << K[i] << ' ' << cnt << '\n';
        if (cnt < K[i]) return 0;
    }
    return 1;
}

bool gw = 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());

   // bool bres = brute(m,k);
    //if (n <=1000) cout << bres << ' '; 

    int res = n+1;
    vector<pii> act;
    act.pb({0,0});
   // cout << M << ": ";
   //// for (int i = 0; i < m; i++) cout << k[i] << " ";
   // cout << '\n';
   // cout << bet({0,0}, {1,2}) << '\n';
  //  cout << bet({1,2}, {2,3}) << '\n';
    for (int i = 0; i < m; i++){
     //   cout << sz(act) << "-";
        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];
      //  cout << act.back().f << "-" << k[i] << ',' << cur << " " << query(roots[k[i]], k[i]) << " " << query(roots[act.back().f],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);
    }
    //cout << '\n';
   // if ((res>=0) != bres) cout << "UHO\n", gw = 0;
    return (res>=0);
}

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