oj.uz

Submission #674328

# Submission time Handle Problem Language Result Execution time Memory
674328 2022-12-23T17:33:07 Z YENGOYAN Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 207340 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  M = m + 1;
    int a = get(l, m, 0, s - 1, 0), b = get_mst(M, 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 L = max(lx, l), R = min(rx, r);
    int  M = m + 1;
    int a = get(L, m, 0, s - 1, 0), b = get_mst(M, 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";
//        }
        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 0 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 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 356 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 0 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 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 13 ms 680 KB Output is correct
12 Correct 18 ms 1484 KB Output is correct
13 Correct 21 ms 1492 KB Output is correct
14 Correct 30 ms 1564 KB Output is correct
15 Correct 29 ms 1572 KB Output is correct
16 Correct 24 ms 1492 KB Output is correct
17 Correct 14 ms 1120 KB Output is correct
18 Correct 23 ms 1492 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3076 ms 207340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1090 ms 22900 KB Output is correct
2 Correct 997 ms 23040 KB Output is correct
3 Correct 1031 ms 23020 KB Output is correct
4 Correct 962 ms 23068 KB Output is correct
5 Correct 1008 ms 23008 KB Output is correct
6 Correct 817 ms 22960 KB Output is correct
7 Correct 808 ms 22840 KB Output is correct
8 Correct 778 ms 22756 KB Output is correct
9 Correct 136 ms 1868 KB Output is correct
10 Correct 744 ms 22636 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 13 ms 680 KB Output is correct
12 Correct 18 ms 1484 KB Output is correct
13 Correct 21 ms 1492 KB Output is correct
14 Correct 30 ms 1564 KB Output is correct
15 Correct 29 ms 1572 KB Output is correct
16 Correct 24 ms 1492 KB Output is correct
17 Correct 14 ms 1120 KB Output is correct
18 Correct 23 ms 1492 KB Output is correct
19 Correct 2425 ms 48752 KB Output is correct
20 Correct 2414 ms 48576 KB Output is correct
21 Correct 2122 ms 48388 KB Output is correct
22 Correct 2101 ms 48240 KB Output is correct
23 Correct 2099 ms 48468 KB Output is correct
24 Correct 1922 ms 48092 KB Output is correct
25 Correct 1988 ms 48184 KB Output is correct
26 Correct 2173 ms 48404 KB Output is correct
27 Correct 2150 ms 48396 KB Output is correct
28 Correct 2199 ms 48512 KB Output is correct
29 Correct 2243 ms 48688 KB Output is correct
30 Correct 2319 ms 48384 KB Output is correct
31 Correct 2268 ms 48384 KB Output is correct
32 Correct 2263 ms 48468 KB Output is correct
33 Correct 2420 ms 48472 KB Output is correct
34 Correct 1891 ms 47992 KB Output is correct
35 Correct 1872 ms 48108 KB Output is correct
36 Correct 1869 ms 47904 KB Output is correct
37 Correct 1822 ms 47824 KB Output is correct
38 Correct 1837 ms 48048 KB Output is correct
39 Correct 1909 ms 47152 KB Output is correct
40 Correct 1057 ms 28996 KB Output is correct
41 Correct 1764 ms 46748 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 1 ms 356 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 13 ms 680 KB Output is correct
12 Correct 18 ms 1484 KB Output is correct
13 Correct 21 ms 1492 KB Output is correct
14 Correct 30 ms 1564 KB Output is correct
15 Correct 29 ms 1572 KB Output is correct
16 Correct 24 ms 1492 KB Output is correct
17 Correct 14 ms 1120 KB Output is correct
18 Correct 23 ms 1492 KB Output is correct
19 Execution timed out 3076 ms 207340 KB Time limit exceeded
20 Halted 0 ms 0 KB -