제출 #1142969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142969		idiotcomputer	팀들 (IOI15_teams)	C++20	0 / 100	1238 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 (l1+r1 - l2 - r2 <= v) return c->l;
    if (c->l == c->r) return n+1;

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

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]) 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());

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

    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';
    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];
       // cout << k[i] << ',' << cur << " ";
        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";
    return (res>=0);
}
/*

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;  
   // cout << N << '\n';
    int A[N];
    int B[N];
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    init(N,A,B);

    int q;
    cin >> q;
   // cout << q << '\n';
    int m;
    for (int i = 0; i < q; i++){
        cin >> m;
        int k[m];
        for (int j = 0; j < m; j++) cin >> k[j];
      //  cout << m <<" ";
      //  for (int j = 0; j < m; j++) cout << k[j] << " ";
      //  cout << '\n';
        int cc = can(m,k);
//cout <<can(m,k) << "\n";
    }
    return 0;
}*/

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