Submission #424159

#	Time	Username	Problem	Language	Result	Execution time	Memory
424159		ocarima	Teams (IOI15_teams)	C++14	0 / 100	928 ms	106092 KiB

teams

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

using namespace std;

#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define repa(i, a, b) for(int i = (a); i >= (b); --i)

#define MAX_N 500002

vector<int> st[1 << 20];
int offset, maxN;

void init(int N, int A[], int B[]) {
    maxN = N;
    offset = 1;
    while (offset < N) offset <<= 1;

    rep(i, 0, N - 1) st[offset + B[i] - 1].emplace_back(A[i]);
    rep(i, 0, N - 1) if (st[offset + i].size()) sort(st[offset + i].begin(), st[offset + i].end());

    repa(i, offset - 1, 1) merge(st[i * 2].begin(), st[i * 2].end(), st[i * 2 + 1].begin(), st[i * 2 + 1].end(), back_inserter(st[i]));
}

int cuenta(int nodo, int s, int e, int up, int down, int r){
    if (s > up || e < down) return 0;
    if (s >= down && e <= up){
        int ini, fin, mitad, cnt;
        ini = 0;
        fin = (int)st[nodo].size() - 1;
        cnt = 0;
        while (ini <= fin){
            mitad = (ini + fin) / 2;
            if (st[nodo][mitad] <= r){
                cnt = mitad + 1;
                ini = mitad + 1;
            }
            else fin = mitad - 1;
        }
        return cnt;
    }

    int mitad = (s + e) / 2;
    return cuenta(nodo * 2, s, mitad, up, down, r) + cuenta(nodo * 2 + 1, mitad + 1, e, up, down, r);
}

int can(int M, int K[]) {

    sort(K, K + M);

    int acarreo, total;

    acarreo = 0;
    rep(i, 0, M - 1){
        total = cuenta(1, 1, offset, maxN, K[i], K[i]);

        total -= acarreo;
        if (total < K[i]){
            return 0;
        }

        if (i < M - 1 && K[i] == K[i + 1]) acarreo += K[i];
        else if (i < M - 1){
            total = cuenta(1, 1, offset, K[i + 1] - 1, K[i], K[i]);
            acarreo = acarreo + K[i] - total;
            if (acarreo < 0) acarreo = 0;
        }
    }

	return 1;
}

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