Submission #593734

#	Time	Username	Problem	Language	Result	Execution time	Memory
593734		davi_bart	Teams (IOI15_teams)	C++17	0 / 100	1094 ms	104356 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) {
            return {s[pos].k[0] <= val, l};
        }
        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(), [](auto &a, auto &b) {
        if (a.se == b.se) return a.fi < b.fi;
        return a.se < b.se;
    });
    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 can(int M, int K[]) {
    sort(K, K + M);
    int pos = 0;
    // cout << endl << endl;
    for (int i = 0; i < M; i++) {
        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:24:72: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   24 |             int u = upper_bound(s[pos].k.begin(), s[pos].k.end(), val) - s[pos].k.begin();
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'void segment::build(int, int, int, std::vector<int>&)':
teams.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if (l < x.size()) s[pos].k.pb(x[l]);
      |                 ~~^~~~~~~~~~
teams.cpp: In function 'int indice(int)':
teams.cpp:71:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   71 |     int l = 0, r = v.size();
      |                    ~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         if (q > v.size()) return 0;
      |             ~~^~~~~~~~~~

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