oj.uz

Submission #674156

# Submission time Handle Problem Language Result Execution time Memory
674156 2022-12-23T10:37:47 Z YENGOYAN Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 2570 ms 205180 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 });
    //qryseg[u] = max(qryseg[u], 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); 
    //for (int i = 0; i < qryseg.size(); ++i) cout << qryseg[i] << " ";
    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";
        // seg l...r minimum to get from l to r
        // там где есть бейлый ворон 
        // там всегда мы найдём покой
        // TGEBV TVMNP
        // ТГЕБВ ТВМНП 
        
    }
}

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 316 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 320 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 2 ms 328 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 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 320 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 2 ms 328 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 18 ms 1504 KB Output is correct
13 Correct 19 ms 1524 KB Output is correct
14 Correct 28 ms 1564 KB Output is correct
15 Correct 30 ms 1492 KB Output is correct
16 Correct 24 ms 1528 KB Output is correct
17 Correct 13 ms 1132 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 Incorrect 1251 ms 205180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 21212 KB Output is correct
2 Correct 919 ms 23168 KB Output is correct
3 Correct 922 ms 22992 KB Output is correct
4 Correct 933 ms 23108 KB Output is correct
5 Correct 910 ms 23068 KB Output is correct
6 Correct 791 ms 22736 KB Output is correct
7 Correct 756 ms 22852 KB Output is correct
8 Correct 703 ms 22640 KB Output is correct
9 Correct 131 ms 1912 KB Output is correct
10 Correct 704 ms 22800 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 316 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 320 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 2 ms 328 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 18 ms 1504 KB Output is correct
13 Correct 19 ms 1524 KB Output is correct
14 Correct 28 ms 1564 KB Output is correct
15 Correct 30 ms 1492 KB Output is correct
16 Correct 24 ms 1528 KB Output is correct
17 Correct 13 ms 1132 KB Output is correct
18 Correct 23 ms 1492 KB Output is correct
19 Correct 2381 ms 46924 KB Output is correct
20 Correct 2570 ms 47004 KB Output is correct
21 Correct 2157 ms 46932 KB Output is correct
22 Correct 1976 ms 46976 KB Output is correct
23 Correct 1949 ms 47068 KB Output is correct
24 Correct 1763 ms 46676 KB Output is correct
25 Correct 1813 ms 46768 KB Output is correct
26 Correct 1978 ms 46688 KB Output is correct
27 Correct 2011 ms 46696 KB Output is correct
28 Correct 2041 ms 46616 KB Output is correct
29 Correct 2059 ms 46660 KB Output is correct
30 Correct 2051 ms 46596 KB Output is correct
31 Correct 2066 ms 46680 KB Output is correct
32 Correct 2093 ms 46616 KB Output is correct
33 Correct 2061 ms 46896 KB Output is correct
34 Correct 1672 ms 46724 KB Output is correct
35 Correct 1712 ms 46632 KB Output is correct
36 Correct 1710 ms 46620 KB Output is correct
37 Correct 1677 ms 46580 KB Output is correct
38 Correct 1714 ms 46660 KB Output is correct
39 Correct 1691 ms 46692 KB Output is correct
40 Correct 954 ms 29292 KB Output is correct
41 Correct 1597 ms 46568 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 316 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 320 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 2 ms 328 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 18 ms 1504 KB Output is correct
13 Correct 19 ms 1524 KB Output is correct
14 Correct 28 ms 1564 KB Output is correct
15 Correct 30 ms 1492 KB Output is correct
16 Correct 24 ms 1528 KB Output is correct
17 Correct 13 ms 1132 KB Output is correct
18 Correct 23 ms 1492 KB Output is correct
19 Incorrect 1251 ms 205180 KB Output isn't correct
20 Halted 0 ms 0 KB -