oj.uz

Submission #674079

# Submission time Handle Problem Language Result Execution time Memory
674079 2022-12-22T22:27:48 Z YENGOYAN Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 193156 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;
vector<vector<int>> mst;

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));
}

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));
}

bool daq(int l, int r, int w) {
    if (l == r) return 1;
    int m = (l + r) / 2;
    bool f = daq(l, m, w), t = daq(m + 1, r, w);
    if (!f || !t) return 0;
    int mx = get(l, m, 0, s - 1, 0), mx_ = get_mst(m + 1, r, 0, s - 1, mx, 0);
    if (mx <= mx_ || mx_ == -1) return 1;
    return (mx + mx_) <= w;
}

void solve() {
    cin >> n >> m;
    v = vector<int>(n);
    while (s < n) s <<= 1;
    seg = vector<int>(2 * s, -1);
    mst = vector<vector<int>>(2 * s);
    for (int i = 0; i < n; ++i) cin >> v[i];
    build(0, s - 1, 0), build_mst(0, s - 1, 0); 
    while (m--) {
        int l, r, w; cin >> l >> r >> w;
        cout << daq(--l, --r, 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:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (i < a.size() && j < b.size()) {
      |            ~~^~~~~~~~~~
sortbooks.cpp:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     while (i < a.size() && j < b.size()) {
      |                            ~~^~~~~~~~~~
sortbooks.cpp:65:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while (i < a.size()) m.push_back(a[i++]);
      |            ~~^~~~~~~~~~
sortbooks.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     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 0 ms 320 KB Output is correct
3 Correct 3 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 12 ms 408 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 29 ms 408 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 33 ms 340 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 3 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 12 ms 408 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 29 ms 408 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 33 ms 340 KB Output is correct
11 Correct 229 ms 644 KB Output is correct
12 Correct 770 ms 1424 KB Output is correct
13 Correct 847 ms 1364 KB Output is correct
14 Correct 1428 ms 1492 KB Output is correct
15 Correct 1421 ms 1488 KB Output is correct
16 Execution timed out 3083 ms 1444 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 3 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 12 ms 408 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 29 ms 408 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 33 ms 340 KB Output is correct
11 Correct 229 ms 644 KB Output is correct
12 Correct 770 ms 1424 KB Output is correct
13 Correct 847 ms 1364 KB Output is correct
14 Correct 1428 ms 1492 KB Output is correct
15 Correct 1421 ms 1488 KB Output is correct
16 Execution timed out 3083 ms 1444 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 3 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 12 ms 408 KB Output is correct
7 Correct 13 ms 340 KB Output is correct
8 Correct 29 ms 408 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 33 ms 340 KB Output is correct
11 Correct 229 ms 644 KB Output is correct
12 Correct 770 ms 1424 KB Output is correct
13 Correct 847 ms 1364 KB Output is correct
14 Correct 1428 ms 1492 KB Output is correct
15 Correct 1421 ms 1488 KB Output is correct
16 Execution timed out 3083 ms 1444 KB Time limit exceeded
17 Halted 0 ms 0 KB -