Submission #619709

#	Time	Username	Problem	Language	Result	Execution time	Memory
619709		someone	Teams (IOI15_teams)	C++14	0 / 100	33 ms	13560 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int deb, fin, val, l = -1, r = -1;
};

const int N = 1 << 3;

vector<Node> node;
vector<int> posFin[N];
int root[N], nbFin[N], nbDeb[N];

int nodeCopy(int id) {
    int i = node.size();
    node.push_back(node[id]);
    return i;
}

int newNode(int deb, int fin) {
    int i = node.size();
    node.push_back({deb, fin, 0});
    return i;
}

int add(int i, int pos) {
    if(pos < node[i].deb || node[i].fin <= pos)
        return i;
    i = nodeCopy(i);
    node[i].val++;
    if(node[i].fin - node[i].deb == 1)
        return i;

    int mid = (node[i].deb + node[i].fin) / 2;
    if(node[i].l == -1) {
        int x = newNode(node[i].deb, mid);
        node[i].l = x;
    }
    if(node[i].r == -1) {
        int x = newNode(mid, node[i].fin);
        node[i].r = x;
    }
    int left = add(node[i].l, pos),
        right = add(node[i].r, pos);
    node[i].l = left, node[i].r = right;
    return i;
}

int getSum(int i, int deb, int fin) {
    if(i == -1)
        return 0;
    if(deb <= node[i].deb && node[i].fin <= fin)
        return node[i].val;
    if(fin <= node[i].deb || node[i].fin <= deb)
        return 0;
    return getSum(node[i].l, deb, fin) + getSum(node[i].r, deb, fin);
}

int getId(int i, int search) {
    if(node[i].fin - node[i].deb == 1)
        return node[i].deb;
    if(node[i].l == -1)
        return getId(node[i].r, search);
    if(search <= node[node[i].l].val)
        return getId(node[i].l, search);
    return getId(node[i].r, search - node[node[i].l].val);
}

void init(int n, int A[], int B[]) {
    for(int i = 0; i < n; i++) {
        B[i]++;
        nbDeb[A[i]]++;
        nbFin[B[i]]++;
        posFin[A[i]].push_back(B[i]);
    }
    for(int i = 1; i < N; i++) {
        nbDeb[i] += nbDeb[i-1];
        nbFin[i] += nbFin[i-1];
    }

    root[0] = 0;
    node.push_back({0, N, 0});
    for(int i = 1; i <= n; i++) {
        root[i] = root[i-1];
        for(int j : posFin[i])
            root[i] = add(root[i], j);
    }
}

int can(int n, int k[]) {
	sort(k, k + n);

    int preK = 0, last = 0, nbPre = 0;
    for(int i = 0; i < n; i++) {
        //trouver cb d'intervalles qu'on aurait pu prendre ont ete pris
        int taken = getSum(root[preK], k[i]+1, last);
        if(last >= k[i]+1)
            taken += nbPre;

        //l'id du dernier pris (1-indexed)
        int id = nbFin[k[i]] + taken + k[i];

        if(id > nbDeb[k[i]])
            return 0;

        //trouver le dernier pris
        last = getId(root[k[i]], id);
        nbPre = id - getSum(root[k[i]], 0, last);

        preK = k[i];
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int nodeCopy(int)':
teams.cpp:16:22: warning: conversion from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |     int i = node.size();
      |             ~~~~~~~~~^~
teams.cpp: In function 'int newNode(int, int)':
teams.cpp:22:22: warning: conversion from 'std::vector<Node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   22 |     int i = node.size();
      |             ~~~~~~~~~^~

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