oj.uz

Submission #619850

# Submission time Handle Problem Language Result Execution time Memory
619850 2022-08-02T16:32:57 Z someone Teams (IOI15_teams) C++14
34 / 100
 4000 ms 50548 KB 
#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;*/
}

Compilation message

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12628 KB Output is correct
2 Correct 7 ms 12616 KB Output is correct
3 Correct 7 ms 12628 KB Output is correct
4 Correct 7 ms 12616 KB Output is correct
5 Correct 7 ms 12640 KB Output is correct
6 Correct 8 ms 12628 KB Output is correct
7 Correct 7 ms 12628 KB Output is correct
8 Correct 8 ms 12616 KB Output is correct
9 Correct 7 ms 12628 KB Output is correct
10 Correct 8 ms 12636 KB Output is correct
11 Correct 7 ms 12628 KB Output is correct
12 Correct 8 ms 12628 KB Output is correct
13 Correct 8 ms 12620 KB Output is correct
14 Correct 8 ms 12628 KB Output is correct
15 Correct 8 ms 12628 KB Output is correct
16 Correct 11 ms 12628 KB Output is correct
17 Correct 7 ms 12532 KB Output is correct
18 Correct 7 ms 12628 KB Output is correct
19 Correct 9 ms 12628 KB Output is correct
20 Correct 7 ms 12620 KB Output is correct
21 Correct 9 ms 12628 KB Output is correct
22 Correct 10 ms 12628 KB Output is correct
23 Correct 9 ms 12628 KB Output is correct
24 Correct 8 ms 12632 KB Output is correct
25 Correct 7 ms 12512 KB Output is correct
26 Correct 8 ms 12580 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15292 KB Output is correct
2 Correct 22 ms 15296 KB Output is correct
3 Correct 49 ms 19568 KB Output is correct
4 Correct 26 ms 15828 KB Output is correct
5 Correct 25 ms 14888 KB Output is correct
6 Correct 32 ms 15052 KB Output is correct
7 Correct 17 ms 14932 KB Output is correct
8 Correct 18 ms 14960 KB Output is correct
9 Correct 35 ms 19864 KB Output is correct
10 Correct 35 ms 19472 KB Output is correct
11 Correct 34 ms 19436 KB Output is correct
12 Correct 37 ms 19152 KB Output is correct
13 Correct 38 ms 17844 KB Output is correct
14 Correct 40 ms 19792 KB Output is correct
15 Correct 23 ms 15836 KB Output is correct
16 Correct 22 ms 15308 KB Output is correct
17 Correct 31 ms 16528 KB Output is correct
18 Correct 31 ms 16488 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16092 KB Output is correct
2 Correct 31 ms 16204 KB Output is correct
3 Execution timed out 4083 ms 20276 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 28596 KB Output is correct
2 Correct 100 ms 28624 KB Output is correct
3 Execution timed out 4029 ms 50548 KB Time limit exceeded
4 Halted 0 ms 0 KB -