Submission #593780

#	Time	Username	Problem	Language	Result	Execution time	Memory
593780		davi_bart	Teams (IOI15_teams)	C++14	77 / 100	4094 ms	101960 KiB

teams

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#include "teams.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
// #define int ll
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct segment {
    static const int dim = 1 << 19;
    struct node {
        vector<int> k;
    };
    vector<node> s = vector<node>(2 * dim);
    int query(int pos, int l, int r, int a, int b, int k) {
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) {
            int u = lower_bound(s[pos].k.begin(), s[pos].k.end(), k) - s[pos].k.begin();
            return s[pos].k.size() - u;
        }

        int m = (l + r) / 2;
        return query(2 * pos, l, m, a, b, k) + query(2 * pos + 1, m + 1, r, a, b, k);
    }
    int query(int a, int b, int k) {
        return query(1, 0, dim - 1, a, b, k);
    }

    void build(int pos, int l, int r, vector<int> &x) {
        if (l == r) {
            if (l < x.size()) s[pos].k.pb(x[l]);
            return;
        }
        int m = (l + r) / 2;
        build(2 * pos, l, m, x);
        build(2 * pos + 1, m + 1, r, x);
        s[pos].k.resize(s[2 * pos].k.size() + s[2 * pos + 1].k.size());
        merge(s[2 * pos].k.begin(), s[2 * pos].k.end(), s[2 * pos + 1].k.begin(), s[2 * pos + 1].k.end(), s[pos].k.begin());
    }
    void build(vector<int> &x) {
        build(1, 0, dim - 1, x);
    }

} seg;
vector<pair<int, int>> v;
void init(int N, int A[], int B[]) {
    for (int i = 0; i < N; i++) {
        v.pb({A[i], B[i]});
    }
    sort(v.begin(), v.end());
    vector<int> u;
    for (auto [a, b] : v) {
        u.pb(b);
    }
    seg.build(u);
}
int indice(int k) {
    int l = 0, r = v.size() - 1;
    while (l < r) {
        int m = (l + r + 1) / 2;
        if (v[m].fi > k)
            r = m - 1;
        else
            l = m;
    }
    return l;
}
int big(int M, int K[]) {
    priority_queue<int, vector<int>, greater<int>> q;
    int pos = 0;
    for (int i = 0; i < M; i++) {
        while (pos < v.size() && v[pos].fi <= K[i]) {
            q.push(v[pos].se);
            pos++;
        }
        int rim = K[i];
        while (rim) {
            if (q.empty()) return 0;
            int x = q.top();
            q.pop();
            if (x >= K[i]) rim--;
        }
    }
    return 1;
}
int conta(int a, int b) {
    int x = indice(a);
    return seg.query(0, x, b);
}
int small(int M, int K[]) {
    vector<int> usate(M, 0);
    for (int i = 0; i < M; i++) {
        vector<int> p;
        for (int j = i; j < M; j++) {
            p.pb(conta(K[i], K[j]));
        }
        int tot = 0;
        for (int j = p.size() - 1; j >= 0; j--) {
            p[j] -= tot;
            tot += p[j];
        }
        for (int j = 0; j < p.size(); j++) {
            p[j] -= usate[i + j];
        }

        int rim = K[i];
        for (int j = 0; j < p.size(); j++) {
            if (rim >= p[j]) {
                rim -= p[j];
                usate[i + j] += p[j];
                p[j] = 0;
            } else {
                usate[i + j] += rim;
                rim = 0;
                break;
            }
        }
        if (rim) return 0;
    }
    return 1;
}
int can(int M, int K[]) {
    sort(K, K + M);
    if (accumulate(K, K + M, 0) > v.size()) return 0;
    if (M < 1000)
        return small(M, K);
    else
        return big(M, K);
}

Compilation message (stderr)

teams.cpp: In member function 'int segment::query(int, int, int, int, int, int)':
teams.cpp:21:70: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   21 |             int u = lower_bound(s[pos].k.begin(), s[pos].k.end(), k) - s[pos].k.begin();
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp:22:36: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   22 |             return s[pos].k.size() - u;
      |                    ~~~~~~~~~~~~~~~~^~~
teams.cpp: In member function 'void segment::build(int, int, int, std::vector<int>&)':
teams.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             if (l < x.size()) s[pos].k.pb(x[l]);
      |                 ~~^~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:55:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for (auto [a, b] : v) {
      |               ^
teams.cpp: In function 'int indice(int)':
teams.cpp:61:29: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   61 |     int l = 0, r = v.size() - 1;
      |                    ~~~~~~~~~^~~
teams.cpp: In function 'int big(int, int*)':
teams.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         while (pos < v.size() && v[pos].fi <= K[i]) {
      |                ~~~~^~~~~~~~~~
teams.cpp: In function 'int small(int, int*)':
teams.cpp:101:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  101 |         for (int j = p.size() - 1; j >= 0; j--) {
      |                      ~~~~~~~~~^~~
teams.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int j = 0; j < p.size(); j++) {
      |                         ~~^~~~~~~~~~
teams.cpp:110:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int j = 0; j < p.size(); j++) {
      |                         ~~^~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:127:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     if (accumulate(K, K + M, 0) > v.size()) return 0;
      |         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

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