Submission #939967

#	Time	Username	Problem	Language	Result	Execution time	Memory
939967		LOLOLO	Teams (IOI15_teams)	C++17	0 / 100	4021 ms	72316 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
typedef  long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 100;
const int M = 2e6;
int n;
vector <pair <int, int>> save;
struct node{
    int s = 0;
    int lson, rson;
 
    node() {};
};
 
node seg[M];
int dd = 1, root[N];
 
void build(int id, int l, int r) {
    if (l == r) {
        return;
    }
 
    int m = (l + r) / 2;
    seg[id].lson = dd++;
    seg[id].rson = dd++;
 
    build(seg[id].lson, l, m);
    build(seg[id].rson, m + 1, r);
}
 
void upd(int pid, int id, int l, int r, int v) {
    if (l > v || r < v)
        return;
 
    if (l == r) {
        return;
    }
 
    int m = (l + r) / 2;
    if (v <= m) {
        seg[id].rson = seg[pid].rson;
        seg[id].lson = dd;
        seg[dd].s = seg[seg[pid].lson].s + 1;
        dd++;
        upd(seg[pid].lson, seg[id].lson, l, m, v);
    } else {
        seg[id].lson = seg[pid].lson;
        seg[id].rson = dd;
        seg[dd].s = seg[seg[pid].rson].s + 1;
        dd++;
        upd(seg[pid].rson, seg[id].rson, m + 1, r, v);
    }
}
 
ll get(int id, int l, int r, int u, int v) {
    if (l > v || r < u)
        return 0;
 
    if (l >= u && r <= v) {
        return seg[id].s;
    }
 
    int m = (l + r) / 2;
    return get(seg[id].lson, l, m, u, v) + get(seg[id].rson, m + 1, r, u, v);
}
 
void build() {
    root[0] = 0;
    build(0, 1, n);
 
    int j = 0;
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];
        int lst = root[i - 1];
        while (j < sz(save) && save[j].f <= i) {
            seg[i].s = seg[lst].s + 1;
            upd(lst, root[i], 1, n, save[j].s);
            lst = dd;
            j++;
        }
    }
}
 
void init(int sz, int _a[], int _b[]) {
    n = sz;
    for (int i = 0; i < n; i++) {
        save.emplace_back(_a[i], _b[i]);
    }
    sort(all(save));
    build();
}
 
int can(int m, int v[]) {
    sort(v, v + m);
    vector <int> a;
    for (int i = 0; i < m; i++) {
        a.pb(v[i]);
    }
 
    uniquev(a);
    deque < pair <int, int>> dq;
 
    for (int i = 0; i < sz(a) - 1; i++) {
        dq.push_back({a[i], get(root[a[i]], 1, n, a[i], a[i + 1] - 1)});
    }
 
    for (int i = 0; i < m; i++) {
        int x = v[i];
        while (sz(dq) && x < dq.front().f)
            dq.pop_front();
 
        while (sz(dq)) {
            auto t = dq.front();
            dq.pop_front();
            if (t.f >= x) {
                if (t.s >= x) {
                    t.s -= x;
                    break;
                } else {
                    x -= t.s;
                }
            }
            dq.push_front(t);
        }
 
        if (x) {
            return 0;
        }
    }
 
    return 1;
}
 

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