oj.uz

Submission #593775

# Submission time Handle Problem Language Result Execution time Memory
593775 2022-07-11T15:08:48 Z davi_bart Teams (IOI15_teams) C++14
77 / 100
 4000 ms 102032 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 < 700)
        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 15 ms 24916 KB Output is correct
2 Correct 15 ms 24916 KB Output is correct
3 Correct 15 ms 24968 KB Output is correct
4 Correct 16 ms 24916 KB Output is correct
5 Correct 16 ms 24960 KB Output is correct
6 Correct 15 ms 24916 KB Output is correct
7 Correct 18 ms 24924 KB Output is correct
8 Correct 23 ms 24916 KB Output is correct
9 Correct 16 ms 24964 KB Output is correct
10 Correct 17 ms 24960 KB Output is correct
11 Correct 21 ms 24956 KB Output is correct
12 Correct 23 ms 24916 KB Output is correct
13 Correct 18 ms 24968 KB Output is correct
14 Correct 16 ms 24916 KB Output is correct
15 Correct 15 ms 24880 KB Output is correct
16 Correct 19 ms 24912 KB Output is correct
17 Correct 22 ms 24872 KB Output is correct
18 Correct 16 ms 24916 KB Output is correct
19 Correct 32 ms 24952 KB Output is correct
20 Correct 21 ms 24928 KB Output is correct
21 Correct 19 ms 24916 KB Output is correct
22 Correct 16 ms 24844 KB Output is correct
23 Correct 17 ms 24868 KB Output is correct
24 Correct 18 ms 24948 KB Output is correct
25 Correct 18 ms 24948 KB Output is correct
26 Correct 17 ms 24916 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 39372 KB Output is correct
2 Correct 58 ms 39320 KB Output is correct
3 Correct 64 ms 39352 KB Output is correct
4 Correct 63 ms 39320 KB Output is correct
5 Correct 70 ms 39408 KB Output is correct
6 Correct 61 ms 39296 KB Output is correct
7 Correct 52 ms 39420 KB Output is correct
8 Correct 54 ms 39396 KB Output is correct
9 Correct 47 ms 40016 KB Output is correct
10 Correct 44 ms 40068 KB Output is correct
11 Correct 43 ms 40000 KB Output is correct
12 Correct 45 ms 39384 KB Output is correct
13 Correct 46 ms 39380 KB Output is correct
14 Correct 45 ms 39368 KB Output is correct
15 Correct 57 ms 39304 KB Output is correct
16 Correct 58 ms 39336 KB Output is correct
17 Correct 44 ms 39404 KB Output is correct
18 Correct 50 ms 39288 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 39420 KB Output is correct
2 Correct 130 ms 39360 KB Output is correct
3 Correct 195 ms 42308 KB Output is correct
4 Correct 70 ms 39356 KB Output is correct
5 Correct 3984 ms 39416 KB Output is correct
6 Correct 3360 ms 39424 KB Output is correct
7 Correct 93 ms 39404 KB Output is correct
8 Correct 2663 ms 39420 KB Output is correct
9 Correct 44 ms 40000 KB Output is correct
10 Correct 69 ms 40280 KB Output is correct
11 Correct 176 ms 40368 KB Output is correct
12 Correct 2760 ms 39432 KB Output is correct
13 Correct 655 ms 39412 KB Output is correct
14 Correct 217 ms 40916 KB Output is correct
15 Correct 196 ms 39508 KB Output is correct
16 Correct 195 ms 39504 KB Output is correct
17 Correct 334 ms 39360 KB Output is correct
18 Correct 327 ms 39436 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 97276 KB Output is correct
2 Correct 270 ms 97220 KB Output is correct
3 Correct 627 ms 102032 KB Output is correct
4 Correct 227 ms 97332 KB Output is correct
5 Correct 1828 ms 97380 KB Output is correct
6 Execution timed out 4021 ms 97988 KB Time limit exceeded
7 Halted 0 ms 0 KB -