제출 #619850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619850		someone	팀들 (IOI15_teams)	C++14	34 / 100	4083 ms	50548 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 << 19;

vector<Node> node;
vector<int> posFin[N];
pair<int, int> inter[N];
int n, 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 X, int A[], int B[]) {
    n = X;
    for(int i = 0; i < n; i++)
        inter[i] = {A[i], B[i]};
    sort(inter, inter + n);

    /*
    n = X;
    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 m, int k[]) {
    sort(k, k + m);

    int id = 0;
    multiset<int> fin;
    for(int i = 0; i < m; i++) {
        while(id < n && inter[id].first <= k[i]) {
            fin.insert(inter[id].second);
            id++;
        }
        int nb = k[i];
        while(!fin.empty() && nb) {
            auto it = fin.begin();
            if((*it) >= k[i])
                nb--;
            fin.erase(it);
        }
        if(nb > 0)
            return 0;
    }
    return 1;

/*
	sort(k, k + m);
    int preK = 0, last = 0, nbPre = 0;
    for(int i = 0; i < m; 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;*/
}

컴파일 시 표준 에러 (stderr) 메시지

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

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