제출 #777539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777539		boris_mihov	팀들 (IOI15_teams)	C++17	0 / 100	578 ms	143316 KiB

teams

#include "teams.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 500000 + 10;
const int INF = 1e9;

int n;
struct MST
{
    int a[MAXN];
    int b[MAXN];
    std::vector <int> tree[4*MAXN];

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].push_back(b[l]);
            return;
        } 

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);

        int lPtr = 0, rPtr = 0;
        tree[node].reserve(r - l + 1);
        for (int i = l ; i <= r ; ++i)
        {
            if (lPtr == tree[2*node].size())
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
                continue;
            }

            if (rPtr == tree[2*node + 1].size())
            {
                tree[node].push_back(tree[2*node][lPtr++]);
                continue;
            }

            if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
            {
                tree[node].push_back(tree[2*node][lPtr++]);
            } else
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
            }
        }
    }

    int atLeast(int node, int value)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] < value) l = mid;
            else r = mid;
        }

        return tree[node].size() - r;
    }

    int query(int l, int r, int node, int queryL, int count, int wanted)
    {
        if (r < queryL)
        {
            return 0;
        }

        if (l == r)
        {
            if (count - (b[l] >= wanted) > 0) return (b[l] >= wanted);
            return -l; 
        } 
        
        int mid = (l + r) / 2;
        if (queryL <= l)
        {
            int curr = atLeast(node, wanted);
            if (curr < count)
            {
                return curr;
            }

            int res = query(l, mid, 2*node, queryL, count, wanted);
            if (res < 0) return res;
            assert(res < count);
            return query(mid + 1, r, 2*node, queryL, count - res, wanted);
        }

        int res = query(l, mid, 2*node, queryL, count, wanted);
        if (res < 0) return res;
        assert(res < count);
        return query(mid + 1, r, 2*node, queryL, count - res, wanted);
    }

    void build(int _a[], int _b[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            a[i] = _a[i];
            b[i] = _b[i];
        }

        build(1, n, 1);
    }

    int query(int pos, int k)
    {
        int res = query(1, n, 1, pos, k, k);
        if (res >= 0) return -1;
        res = -res;
        if (a[res] > k) return -1;
        return res + 1;
    }
};

int a[MAXN];
int b[MAXN];
int perm[MAXN];
std::vector <int> v[MAXN];
MST tree;

void init(int N, int A[], int B[]) 
{
    n = N;
    std::iota(perm, perm + n, 0);
    std::sort(perm, perm + n, [&](int x, int y)
    {
        return A[x] < A[y] || (A[x] == A[y] && B[x] < B[y]);
    });

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = A[perm[i - 1]];
        b[i] = B[perm[i - 1]];
    }

    tree.build(a, b);
}

int can(int M, int K[]) 
{
    int pos = 1;
    std::sort(K, K + M);
    for (int i = 0 ; i < M ; ++i)
    {
        pos = tree.query(pos, K[i]);
        if (pos == -1)
        {
            return 0;
        }
    }

    return 1;
}

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

teams.cpp: In member function 'void MST::build(int, int, int)':
teams.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             if (lPtr == tree[2*node].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
teams.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if (rPtr == tree[2*node + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'int MST::atLeast(int, int)':
teams.cpp:60:40: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   60 |         int l = -1, r = tree[node].size(), mid;
      |                         ~~~~~~~~~~~~~~~^~
teams.cpp:68:34: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   68 |         return tree[node].size() - r;
      |                ~~~~~~~~~~~~~~~~~~^~~

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