oj.uz

Submission #593773

# Submission time Handle Problem Language Result Execution time Memory
593773 2022-07-11T15:07:56 Z davi_bart Teams (IOI15_teams) C++14
77 / 100
 4000 ms 102068 KB 
#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 (M < 1000)
        return small(M, K);
    else
        return big(M, K);
}

Compilation message

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++) {
      |                         ~~^~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24916 KB Output is correct
2 Correct 15 ms 24896 KB Output is correct
3 Correct 17 ms 24900 KB Output is correct
4 Correct 21 ms 24864 KB Output is correct
5 Correct 16 ms 24916 KB Output is correct
6 Correct 16 ms 24916 KB Output is correct
7 Correct 16 ms 24912 KB Output is correct
8 Correct 18 ms 24916 KB Output is correct
9 Correct 18 ms 24892 KB Output is correct
10 Correct 15 ms 24844 KB Output is correct
11 Correct 16 ms 24876 KB Output is correct
12 Correct 24 ms 24976 KB Output is correct
13 Correct 18 ms 24964 KB Output is correct
14 Correct 21 ms 24916 KB Output is correct
15 Correct 17 ms 24916 KB Output is correct
16 Correct 16 ms 24976 KB Output is correct
17 Correct 21 ms 24832 KB Output is correct
18 Correct 17 ms 24916 KB Output is correct
19 Correct 16 ms 24916 KB Output is correct
20 Correct 16 ms 24828 KB Output is correct
21 Correct 16 ms 24916 KB Output is correct
22 Correct 16 ms 24888 KB Output is correct
23 Correct 15 ms 24916 KB Output is correct
24 Correct 15 ms 24916 KB Output is correct
25 Correct 16 ms 24892 KB Output is correct
26 Correct 16 ms 24944 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 39360 KB Output is correct
2 Correct 59 ms 39308 KB Output is correct
3 Correct 59 ms 39340 KB Output is correct
4 Correct 58 ms 39372 KB Output is correct
5 Correct 60 ms 39292 KB Output is correct
6 Correct 51 ms 39332 KB Output is correct
7 Correct 41 ms 39428 KB Output is correct
8 Correct 43 ms 39368 KB Output is correct
9 Correct 43 ms 40060 KB Output is correct
10 Correct 43 ms 40604 KB Output is correct
11 Correct 42 ms 40480 KB Output is correct
12 Correct 47 ms 39856 KB Output is correct
13 Correct 46 ms 39808 KB Output is correct
14 Correct 47 ms 39832 KB Output is correct
15 Correct 52 ms 39832 KB Output is correct
16 Correct 54 ms 39912 KB Output is correct
17 Correct 47 ms 39816 KB Output is correct
18 Correct 45 ms 39840 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 39328 KB Output is correct
2 Correct 116 ms 39416 KB Output is correct
3 Correct 180 ms 42292 KB Output is correct
4 Correct 56 ms 39332 KB Output is correct
5 Correct 3888 ms 39420 KB Output is correct
6 Correct 3188 ms 39596 KB Output is correct
7 Correct 88 ms 39508 KB Output is correct
8 Correct 2387 ms 39676 KB Output is correct
9 Correct 43 ms 39996 KB Output is correct
10 Correct 56 ms 41012 KB Output is correct
11 Correct 170 ms 41128 KB Output is correct
12 Correct 2414 ms 40204 KB Output is correct
13 Correct 580 ms 40948 KB Output is correct
14 Correct 202 ms 42784 KB Output is correct
15 Correct 185 ms 40908 KB Output is correct
16 Correct 191 ms 40896 KB Output is correct
17 Correct 357 ms 41012 KB Output is correct
18 Correct 320 ms 40896 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 97380 KB Output is correct
2 Correct 332 ms 97332 KB Output is correct
3 Correct 604 ms 102068 KB Output is correct
4 Correct 219 ms 97276 KB Output is correct
5 Execution timed out 4098 ms 97276 KB Time limit exceeded
6 Halted 0 ms 0 KB -