Submission #107977

#	Time	Username	Problem	Language	Result	Execution time	Memory
107977		PeppaPig	Teams (IOI15_teams)	C++14	77 / 100	4049 ms	523984 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5+5;

struct node {
    int d;
    node *l, *r;
    node() { }
    node(int d, node *l, node *r) : d(d), l(l), r(r) { }
};

node* newleaf(int d) { return new node(d, NULL, NULL); }
node* newpar(node *l, node *r) { return new node(l->d + r->d, l, r); }

int n;
node* t[N];

node* build(int l = 0, int r = N-1) {
    if(l == r) return newleaf(0);
    int mid = (l + r) >> 1;
    return newpar(build(l, mid), build(mid+1, r));
}

node* update(int x, node *p, int l = 0, int r = N-1) {
    if(l == r) return newleaf(p->d + 1);
    int mid = (l + r) >> 1;
    if(x <= mid) return newpar(update(x, p->l, l, mid), p->r);
    else return newpar(p->l, update(x, p->r, mid+1, r));
}

node* erase(int k, node *p, node *pz, int l = 0, int r = N-1) {
    if(r <= k) return pz;
    if(l > k) return p;
    int mid = (l + r) >> 1;
    return newpar(erase(k, p->l, pz->l, l, mid), erase(k, p->r, pz->r, mid+1, r));
}

node* choose(int k, node *all, node *p, int l = 0, int r = N-1) {
    if(l == r) return newleaf(p->d + k);
    int sum = all->l->d - p->l->d, mid = (l + r) >> 1;
    if(sum >= k) return newpar(choose(k, all->l, p->l, l, mid), p->r);
    else return newpar(all->l, choose(k - sum, all->r, p->r, mid+1, r));
}

node *start;
vector<int> coord[N];

void init(int _n, int A[], int B[]) {
    n = _n, t[0] = build();
    for(int i = 0; i < n; i++) coord[A[i]].emplace_back(B[i]);
    for(int i = 1; i <= n; i++) {
        t[i] = erase(i-1, t[i-1], t[0]);
        for(int b : coord[i]) t[i] = update(b, t[i]);
    } 
    start = build();
}

int can(int m, int K[]) {
    sort(K, K+m);
    node *cur = start;
    for(int i = 0; i < m; i++) {
        cur = erase(K[i]-1, cur, t[0]);
        if(t[K[i]]->d - cur->d < K[i]) return 0;
        cur = choose(K[i], t[K[i]], cur);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In constructor 'node::node(int, node*, node*)':
teams.cpp:12:35: warning: declaration of 'r' shadows a member of 'node' [-Wshadow]
     node(int d, node *l, node *r) : d(d), l(l), r(r) { }
                                   ^
teams.cpp:10:15: note: shadowed declaration is here
     node *l, *r;
               ^
teams.cpp:12:35: warning: declaration of 'l' shadows a member of 'node' [-Wshadow]
     node(int d, node *l, node *r) : d(d), l(l), r(r) { }
                                   ^
teams.cpp:10:11: note: shadowed declaration is here
     node *l, *r;
           ^
teams.cpp:12:35: warning: declaration of 'd' shadows a member of 'node' [-Wshadow]
     node(int d, node *l, node *r) : d(d), l(l), r(r) { }
                                   ^
teams.cpp:9:9: note: shadowed declaration is here
     int d;
         ^

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