Submission #593768

#	Time	Username	Problem	Language	Result	Execution time	Memory
593768		davi_bart	Teams (IOI15_teams)	C++14	21 / 100	4089 ms	97748 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);
    pair<int, int> query(int pos, int l, int r, int a, int b, int val, int k) {
        if (b < l || r < a) return {0, 1e9};
        if (l == r) {
            if (s[pos].k.size() && s[pos].k[0] <= val) {
                if (k == 1) return {1, l};
                return {1, 1e9};
            }
            return {0, 1e9};
        }
        // if (a <= l && r <= b) {
        //     int u = upper_bound(s[pos].k.begin(), s[pos].k.end(), val) - s[pos].k.begin();
        //     if (u < k) return {u, 1e9};
        // }

        int m = (l + r) / 2;
        auto [x, y] = query(2 * pos, l, m, a, b, val, k);
        if (x == k) return {k, y};
        auto [x1, y1] = query(2 * pos + 1, m + 1, r, a, b, val, k - x);
        if (x + x1 < k) return {x + x1, 1e9};
        return {k, y1};
    }
    int query(int a, int val, int k) {
        return query(1, 0, dim - 1, a, dim - 1, val, k).se;
    }

    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(a);
    }
    seg.build(u);
}
int indice(int k) {
    int l = 0, r = v.size();
    while (l < r) {
        int m = (l + r) / 2;
        if (v[m].se >= k)
            r = m;
        else
            l = m + 1;
    }
    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 tot = 0;
    for (auto [x, y] : v) {
        tot += (x <= a && b <= y);
    }
    return tot;
}
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;
        // int k = conta(K[i], K[i]);
        // if (k - usate < K[i]) return 0;
        // if (i < M - 1) {
        //     int k1 = conta(K[i], K[i + 1]);
        //     cout << k << " " << usate << " " << k1 << endl;
        //     usate = k1 - min(k - usate, K[i] - (k - usate - k1));
        // }
    }
    return 1;
}
int can(int M, int K[]) {
    sort(K, K + M);
    return small(M, K);
    int pos = 0;
    // cout << endl << endl;
    for (int i = 0; i < M; i++) {
        int rim = K[i];
        while (rim) {
            if (pos >= v.size()) return 0;
            if (v[pos].fi <= K[i] && v[pos].se >= K[i]) rim--;
            pos++;
        }
        // pos = max(pos, indice(K[i]));
        // int q = seg.query(pos, K[i], K[i]);
        // // cout << pos << "," << q << "    ";
        // if (q > v.size()) return 0;
        // pos = q + 1;
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'std::pair<int, int> segment::query(int, int, int, int, int, int, int)':
teams.cpp:33:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |         auto [x, y] = query(2 * pos, l, m, a, b, val, k);
      |              ^
teams.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         auto [x1, y1] = query(2 * pos + 1, m + 1, r, a, b, val, k - x);
      |              ^
teams.cpp: In member function 'void segment::build(int, int, int, std::vector<int>&)':
teams.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if (l < x.size()) s[pos].k.pb(x[l]);
      |                 ~~^~~~~~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:66:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for (auto [a, b] : v) {
      |               ^
teams.cpp: In function 'int indice(int)':
teams.cpp:72:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   72 |     int l = 0, r = v.size();
      |                    ~~~~~~^~
teams.cpp: In function 'int big(int, int*)':
teams.cpp:86: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]
   86 |         while (pos < v.size() && v[pos].fi <= K[i]) {
      |                ~~~~^~~~~~~~~~
teams.cpp: In function 'int conta(int, int)':
teams.cpp:102:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |     for (auto [x, y] : v) {
      |               ^
teams.cpp: In function 'int small(int, int*)':
teams.cpp:115:31: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  115 |         for (int j = p.size() - 1; j >= 0; j--) {
      |                      ~~~~~~~~~^~~
teams.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int j = 0; j < p.size(); j++) {
      |                         ~~^~~~~~~~~~
teams.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 0; j < p.size(); j++) {
      |                         ~~^~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:154:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             if (pos >= v.size()) return 0;
      |                 ~~~~^~~~~~~~~~~

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