Submission #1053006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053006		onbert	Teams (IOI15_teams)	C++17	0 / 100	1192 ms	263584 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
    int val, lpt, rpt;
};
const int maxn = 5e5 + 5, maxN = 2e6 + 5;
int n;

vector<node> seg[maxN];
int pos[maxn];
void build(int id, int l, int r) {
    seg[id] = {{0, 0, 0}};
    if (l==r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int l, int r, int target) {
    if (r<target || target<l) return;
    if (l==r) {
        int val = seg[id].back().val + 1;
        seg[id].push_back({val, 0, 0});
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target); update(id*2+1, mid+1, r, target);
    seg[id].push_back({seg[id*2].back().val + seg[id*2+1].back().val, (int)seg[id*2].size()-1, (int)seg[id*2+1].size()-1});
}
int qry(int id, int pt, int l, int r, int findl, int findr) {
    if (r<findl || findr<l) return 0;
    if (findl<=l && r<=findr) return seg[id][pt].val;
    int mid = (l+r)/2;
    return qry(id*2, seg[id][pt].lpt, l, mid, findl, findr) + qry(id*2+1, seg[id][pt].rpt, mid+1, r, findl, findr);
}

void init(int N, int A[], int B[]) {
    n = N;
    build(1, 1, n);
    vector<int> vec[n+1];
    for (int i=0;i<n;i++) vec[A[i]].push_back(B[i]);
    for (int i=1;i<=n;i++) {
        for (int j:vec[i]) update(1, 1, n, j);
        pos[i] = (int)seg[1].size() - 1;
    }
}

int can(int m, int a[]) {
	sort(a, a+m);
    int left = 0, last = 0;
    for (int i=0;i<m;i++) {
        left += qry(1, pos[a[i]], 1, n, a[i], n) - qry(1, pos[last], 1, n, a[i], n);
        left -= a[i];
        if (left<0) return 0;
        last = a[i];
    }
    return 1;
}

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