oj.uz

Submission #674207

# Submission time Handle Problem Language Result Execution time Memory
674207 2022-12-23T13:24:52 Z YENGOYAN Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
77 / 100
 3000 ms 216848 KB 
// eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee //
// 271828___182845__904523__53602__ //
// 87___47____13______52____66__24_ //
// 97___75____72______47____09___36 // 
// 999595_____74______96____69___67 // 
// 62___77____24______07____66__30_ // 
// 35___35____47______59____45713__ //
// eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee //
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_map>
#include <cmath>
#include <climits>
#include <algorithm>
#include <random>
#include <queue>
#include <deque>
#include <iomanip>
#include <string>
#include <tuple>
#include <bitset>
#include <chrono>
#include <ctime>
#include <fstream>
#include <stack>
#include <cstdio>

using namespace std;
using ll = long long;
const int N = 1e5 + 5;
const ll mod = 1e9 + 7, inf = 1e18;

int n, m, s = 1;
vector<int> seg, v, qryseg;
vector<vector<int>> mst;

vector<int> merge(vector<int>& a, vector<int>& b) {
    vector<int> m;
    int i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] < b[j]) m.push_back(a[i++]);
        else m.push_back(b[j++]);
    }
    while (i < a.size()) m.push_back(a[i++]);
    while (j < b.size()) m.push_back(b[j++]);
    return m;
}

void build_mst(int l, int r, int u) {
    if (l == r) {
        if (l < n) mst[u].push_back(v[l]);
        return;
    }
    int m = (l + r) / 2;
    build_mst(l, m, 2 * u + 1), build_mst(m + 1, r, 2 * u + 2);
    mst[u] = merge(mst[2 * u + 1], mst[2 * u + 2]);
}

int get_mst(int l, int r, int lx, int rx, int k, int u) {
    if (lx >= l && rx <= r) {
        int id = lower_bound(mst[u].begin(), mst[u].end(), k) - mst[u].begin() - 1;
        if (id == -1) return -1;
        return mst[u][id];
    }
    if (lx > r || rx < l) return -1;
    int m = (lx + rx) / 2;
    return max(get_mst(l, r, lx, m, k, 2 * u + 1), get_mst(l, r, m + 1, rx, k, 2 * u + 2));
}

void build(int l, int r, int u) {
    if (l == r) {
        if (l < n) seg[u] = v[l];
        return;
    }
    int m = (l + r) / 2;
    build(l, m, 2 * u + 1), build(m + 1, r, 2 * u + 2);
    seg[u] = max(seg[2 * u + 1], seg[2 * u + 2]);
}

int get(int l, int r, int lx, int rx, int u) {
    if (lx >= l && rx <= r) return seg[u];
    if (lx > r || rx < l) return -1;
    int m = (lx + rx) / 2;
    return max(get(l, r, lx, m, 2 * u + 1), get(l, r, m + 1, rx, 2 * u + 2));
}

void build_qry(int l, int r, int u) {
    if (l == r) {
        qryseg[u] = 0;
        return;
    }
    int m = (l + r) / 2;
    build_qry(l, m, 2 * u + 1), build_qry(m + 1, r, 2 * u + 2);
    qryseg[u] = max(qryseg[2 * u + 1], qryseg[2 * u + 2]);
    int a = get(l, m, 0, s - 1, 0), b = get_mst(m + 1, r, 0, s - 1, a, 0);
    if (b != -1) qryseg[u] = max(qryseg[u], a + b);
}

int get_qry(int l, int r, int lx, int rx, int u) {
    if (lx >= l && rx <= r) return qryseg[u];
    if (lx > r || rx < l) return -1;
    int m = (lx + rx) / 2;
    int a = get(max(lx, l), m, 0, s - 1, 0), b = get_mst(m + 1, min(rx, r), 0, s - 1, a, 0);
    if (b == -1) return max(get_qry(l, r, lx, m, 2 * u + 1), get_qry(l, r, m + 1, rx, 2 * u + 2));
    return max({ get_qry(l, r, lx, m, 2 * u + 1), get_qry(l, r, m + 1, rx, 2 * u + 2), a + b });
}

void solve() {
    cin >> n >> m;
    v = vector<int>(n);
    while (s < n) s <<= 1;
    qryseg = seg = vector<int>(2 * s, -1);
    mst = vector<vector<int>>(2 * s);
    int mn = 2e9;
    for (int i = 0; i < n; ++i) cin >> v[i], mn = min(mn, v[i]);
    vector<int> ids;
    for (int i = 1; i < n; ++i) {
        if (v[i] < v[i - 1]) ids.push_back(i);
    }
    ids.push_back(n);
    build(0, s - 1, 0), build_mst(0, s - 1, 0), build_qry(0, s - 1, 0);
    while (m--) {
        int l, r, w; cin >> l >> r >> w;
        if (w < mn) {
            int id = upper_bound(ids.begin(), ids.end(), --l) - ids.begin();
            id = ids[id] - 1;
            if (id < --r) cout << "0\n";
            else cout << "1\n";
        }
        else cout << (get_qry(--l, --r, 0, s - 1, 0) <= w) << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    //int _; cin >> _; while (_--)
    solve();
}

Compilation message

sortbooks.cpp: In function 'std::vector<int> merge(std::vector<int>&, std::vector<int>&)':
sortbooks.cpp:44:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while (i < a.size() && j < b.size()) {
      |            ~~^~~~~~~~~~
sortbooks.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     while (i < a.size() && j < b.size()) {
      |                            ~~^~~~~~~~~~
sortbooks.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     while (i < a.size()) m.push_back(a[i++]);
      |            ~~^~~~~~~~~~
sortbooks.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while (j < b.size()) m.push_back(b[j++]);
      |            ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 16 ms 1492 KB Output is correct
13 Correct 21 ms 1528 KB Output is correct
14 Correct 28 ms 1484 KB Output is correct
15 Correct 35 ms 1580 KB Output is correct
16 Correct 28 ms 1520 KB Output is correct
17 Correct 13 ms 1128 KB Output is correct
18 Correct 22 ms 1496 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1264 ms 209176 KB Output is correct
2 Correct 1358 ms 209656 KB Output is correct
3 Correct 1302 ms 206292 KB Output is correct
4 Correct 1265 ms 206296 KB Output is correct
5 Correct 1049 ms 204432 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 22868 KB Output is correct
2 Correct 896 ms 23260 KB Output is correct
3 Correct 948 ms 23064 KB Output is correct
4 Correct 988 ms 22896 KB Output is correct
5 Correct 981 ms 22992 KB Output is correct
6 Correct 800 ms 22860 KB Output is correct
7 Correct 761 ms 22960 KB Output is correct
8 Correct 736 ms 22680 KB Output is correct
9 Correct 129 ms 1824 KB Output is correct
10 Correct 778 ms 22676 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 16 ms 1492 KB Output is correct
13 Correct 21 ms 1528 KB Output is correct
14 Correct 28 ms 1484 KB Output is correct
15 Correct 35 ms 1580 KB Output is correct
16 Correct 28 ms 1520 KB Output is correct
17 Correct 13 ms 1128 KB Output is correct
18 Correct 22 ms 1496 KB Output is correct
19 Correct 2482 ms 47356 KB Output is correct
20 Correct 2653 ms 47300 KB Output is correct
21 Correct 2045 ms 47052 KB Output is correct
22 Correct 2037 ms 47148 KB Output is correct
23 Correct 2009 ms 47332 KB Output is correct
24 Correct 1978 ms 46700 KB Output is correct
25 Correct 1894 ms 46720 KB Output is correct
26 Correct 2009 ms 46864 KB Output is correct
27 Correct 2108 ms 46988 KB Output is correct
28 Correct 2068 ms 46916 KB Output is correct
29 Correct 2135 ms 46996 KB Output is correct
30 Correct 2164 ms 46980 KB Output is correct
31 Correct 2174 ms 47156 KB Output is correct
32 Correct 2142 ms 46836 KB Output is correct
33 Correct 2193 ms 46988 KB Output is correct
34 Correct 1768 ms 46692 KB Output is correct
35 Correct 1756 ms 46580 KB Output is correct
36 Correct 1711 ms 46468 KB Output is correct
37 Correct 1738 ms 46528 KB Output is correct
38 Correct 1748 ms 46568 KB Output is correct
39 Correct 1753 ms 45608 KB Output is correct
40 Correct 1037 ms 27512 KB Output is correct
41 Correct 1782 ms 45144 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 16 ms 1492 KB Output is correct
13 Correct 21 ms 1528 KB Output is correct
14 Correct 28 ms 1484 KB Output is correct
15 Correct 35 ms 1580 KB Output is correct
16 Correct 28 ms 1520 KB Output is correct
17 Correct 13 ms 1128 KB Output is correct
18 Correct 22 ms 1496 KB Output is correct
19 Correct 1264 ms 209176 KB Output is correct
20 Correct 1358 ms 209656 KB Output is correct
21 Correct 1302 ms 206292 KB Output is correct
22 Correct 1265 ms 206296 KB Output is correct
23 Correct 1049 ms 204432 KB Output is correct
24 Correct 1020 ms 22868 KB Output is correct
25 Correct 896 ms 23260 KB Output is correct
26 Correct 948 ms 23064 KB Output is correct
27 Correct 988 ms 22896 KB Output is correct
28 Correct 981 ms 22992 KB Output is correct
29 Correct 800 ms 22860 KB Output is correct
30 Correct 761 ms 22960 KB Output is correct
31 Correct 736 ms 22680 KB Output is correct
32 Correct 129 ms 1824 KB Output is correct
33 Correct 778 ms 22676 KB Output is correct
34 Correct 2482 ms 47356 KB Output is correct
35 Correct 2653 ms 47300 KB Output is correct
36 Correct 2045 ms 47052 KB Output is correct
37 Correct 2037 ms 47148 KB Output is correct
38 Correct 2009 ms 47332 KB Output is correct
39 Correct 1978 ms 46700 KB Output is correct
40 Correct 1894 ms 46720 KB Output is correct
41 Correct 2009 ms 46864 KB Output is correct
42 Correct 2108 ms 46988 KB Output is correct
43 Correct 2068 ms 46916 KB Output is correct
44 Correct 2135 ms 46996 KB Output is correct
45 Correct 2164 ms 46980 KB Output is correct
46 Correct 2174 ms 47156 KB Output is correct
47 Correct 2142 ms 46836 KB Output is correct
48 Correct 2193 ms 46988 KB Output is correct
49 Correct 1768 ms 46692 KB Output is correct
50 Correct 1756 ms 46580 KB Output is correct
51 Correct 1711 ms 46468 KB Output is correct
52 Correct 1738 ms 46528 KB Output is correct
53 Correct 1748 ms 46568 KB Output is correct
54 Correct 1753 ms 45608 KB Output is correct
55 Correct 1037 ms 27512 KB Output is correct
56 Correct 1782 ms 45144 KB Output is correct
57 Execution timed out 3030 ms 216848 KB Time limit exceeded
58 Halted 0 ms 0 KB -