Submission #701057

#	Time	Username	Problem	Language	Result	Execution time	Memory
701057		finn__	Teams (IOI15_teams)	C++17	0 / 100	2960 ms	92260 KiB

teams

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

template <typename T>
struct FenwickTree2dOff
{
    vector<vector<T>> t;
    vector<vector<unsigned>> c;
    bool initialized = 0;

    FenwickTree2dOff() {}

    FenwickTree2dOff(size_t n)
    {
        t = vector<vector<T>>(n);
        c = vector<vector<unsigned>>(n);
    }

    void initialize()
    {
        initialized = 1;
        for (size_t i = 0; i < t.size(); i++)
        {
            sort(c[i].begin(), c[i].end());
            c[i].resize(unique(c[i].begin(), c[i].end()) - c[i].begin());
            t[i] = vector<T>(c[i].size(), 0);
        }
    }

    void update(int64_t i, int64_t j, T x)
    {
        i++, j++;
        while (i <= t.size())
        {
            if (!initialized)
                c[i - 1].push_back(j);
            else
            {
                int64_t k = upper_bound(c[i - 1].begin(), c[i - 1].end(), j) - c[i].begin();
                while (k <= c[i - 1].size())
                {
                    t[i - 1][k - 1] += x;
                    k += k & -k;
                }
            }
            i += i & -i;
        }
    }

    T prefix_sum(int64_t i, int64_t j)
    {
        T x = 0;
        i++, j++;
        while (i)
        {
            int64_t k = upper_bound(c[i - 1].begin(), c[i - 1].end(), j) - c[i - 1].begin();
            while (k)
            {
                x += t[i - 1][k - 1];
                k -= k & -k;
            }
            i -= i & -i;
        }
        return x;
    }

    T range_sum(int64_t i1, int64_t i2, int64_t j1, int64_t j2)
    {
        return prefix_sum(j1, j2) - prefix_sum(i1 - 1, j2) - prefix_sum(j1, i2 - 1) + prefix_sum(i1 - 1, i2 - 1);
    }
};

FenwickTree2dOff<unsigned> tree;
int n;

void init(int N, int A[], int B[])
{
    n = N;
    tree = FenwickTree2dOff<unsigned>(N + 2);
    for (size_t i = 0; i < N; i++)
        tree.update(A[i], B[i], 1);
    tree.initialize();
}

int can(int M, int K[])
{
    sort(K, K + M);
    int y_lim = 1, residual = 0;

    for (size_t i = 0; i < M; i++)
    {
        int a = max(y_lim, K[i]), b = n + 1, last_num = 0;
        while (a < b) // Binary search for the highest end index needed.
        {
            int const y = (a + b) / 2;
            int const x = tree.range_sum(1, y, K[i], n);
            if (x >= K[i] - residual)
                b = y, last_num = x;
            else
                a = y + 1;
        }
        if (a == n + 1)
            return 0;
        residual = last_num - (K[i] - residual);
        y_lim = a + 1;
    }

    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:81:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |     for (size_t i = 0; i < N; i++)
      |                        ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:91:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |     for (size_t i = 0; i < M; i++)
      |                        ~~^~~
teams.cpp: In instantiation of 'FenwickTree2dOff<T>::FenwickTree2dOff(size_t) [with T = unsigned int; size_t = long unsigned int]':
teams.cpp:80:44:   required from here
teams.cpp:14:29: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   14 |     FenwickTree2dOff(size_t n)
      |                      ~~~~~~~^
teams.cpp:75:5: note: shadowed declaration is here
   75 | int n;
      |     ^
teams.cpp:14:29: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   14 |     FenwickTree2dOff(size_t n)
      |                      ~~~~~~~^
teams.cpp:75:5: note: shadowed declaration is here
   75 | int n;
      |     ^
teams.cpp: In instantiation of 'void FenwickTree2dOff<T>::update(int64_t, int64_t, T) [with T = unsigned int; int64_t = long int]':
teams.cpp:82:34:   required from here
teams.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::vector<unsigned int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while (i <= t.size())
      |                ~~^~~~~~~~~~~
teams.cpp:37:36: warning: conversion from 'int64_t' {aka 'long int'} to 'std::vector<unsigned int>::value_type' {aka 'unsigned int'} may change value [-Wconversion]
   37 |                 c[i - 1].push_back(j);
      |                                    ^
teams.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                 while (k <= c[i - 1].size())
      |                        ~~^~~~~~~~~~~~~~~~~~

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