oj.uz

답안 #501612

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501612 2022-01-04T07:32:01 Z dxz05 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 3000 ms 247572 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()

#define MP make_pair

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

#define tree qrisdfni

struct node{
    int ans = 0;
    int mx = -1;
    vector<int> vec;
    node(){};
} tree[2200000];

int size = 1;

inline int lwb(int x, const vector<int> &v){
    int i = lower_bound(all(v), x) - v.begin() - 1;
    if (i >= 0) return v[i];
    return -1;
}

inline void build(int v, int tl, int tr, const vector<int> &a){
    tree[v].vec.reserve(tr - tl + 1);

    if (tl == tr){
        tree[v].ans = 0;
        tree[v].mx = a[tl - 1];
        tree[v].vec = {a[tl - 1]};
        return;
    }

    int tm = (tl + tr) >> 1;
    build(v + v, tl, tm, a);
    build(v + v + 1, tm + 1, tr, a);

    merge(tree[v].vec, tree[v + v].vec, tree[v + v + 1].vec);
    tree[v].mx = max(tree[v + v].mx, tree[v + v + 1].mx);
    tree[v].ans = max(tree[v + v].ans, tree[v + v + 1].ans);

    int x = lwb(tree[v + v].mx, tree[v + v + 1].vec);
    if (x != -1) tree[v].ans = max(tree[v].ans, tree[v + v].mx + x);
}

inline void init(const vector<int> &a){
    size = a.size();
    build(1, 1, size, a);
}

inline int biggest(int v, int tl, int tr, int l, int r, int key){
    if (l <= tl && tr <= r){
        int x = lwb(key, tree[v].vec);
        return x;
    }
    if (tl > r || tr < l) return -1;
    int tm = (tl + tr) >> 1;
    return max(biggest(v + v, tl, tm, l, r, key), biggest(v + v + 1, tm + 1, tr, l, r, key));
}

inline pair<int, int> get(int v, int tl, int tr, int l, int r){
    if (l <= tl && tr <= r) return MP(tree[v].ans, tree[v].mx);
    if (tl > r || tr < l) return MP(0, -1);
    int tm = (tl + tr) >> 1;
    auto lf = get(v + v, tl, tm, l, r), rg = get(v + v + 1, tm + 1, tr, l, r);
    int ans = max(lf.first, rg.first);
    if (lf.second != -1 && rg.second != -1) {
        int x = biggest(1, 1, size, tm + 1, min(r, tr), lf.second);
        if (x != -1) ans = max(ans, lf.second + x);
    }

    return MP(ans, max(lf.second, rg.second));
}

inline pair<int, int> get(int l, int r){
    return get(1, 1, size, l, r);
}

vector<pair<int, pair<int, int>>> queries[1000001];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int &i : a) cin >> i;

    init(a);

    for (int i = 1; i <= q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        queries[l].emplace_back(r, MP(k, i));
    }

    bitset<1000001> ans;
    for (int l = 1; l <= n; l++){
        if (queries[l].empty()) continue;

        pair<int, int> x = MP(-1, -1);
        for (int i = 0; i < queries[l].size(); i++){
            int r = queries[l][i].first, k = queries[l][i].second.first, ind = queries[l][i].second.second;

            if (i == 0){
                x = get(l, r);
                ans[ind] = x.first <= k;
            } else {
                int pr = queries[l][i - 1].first;

                if (pr == r){
                    ans[ind] = x.first <= k;
                    continue;
                }

                pr++;

                auto y = get(pr, r);
                x.first = max(x.first, y.first);

                int bg = biggest(1, 1, size, pr, r, x.second);
                if (bg != -1) x.first = max(x.first, x.second + bg);
                x.second = max(x.second, y.second);

                ans[ind] = x.first <= k;
            }

        }

    }

    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';

    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for (int i = 0; i < queries[l].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 92776 KB Output is correct
2 Correct 43 ms 92708 KB Output is correct
3 Incorrect 44 ms 92760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 92776 KB Output is correct
2 Correct 43 ms 92708 KB Output is correct
3 Incorrect 44 ms 92760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3080 ms 247572 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 376 ms 107068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 92776 KB Output is correct
2 Correct 43 ms 92708 KB Output is correct
3 Incorrect 44 ms 92760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 92776 KB Output is correct
2 Correct 43 ms 92708 KB Output is correct
3 Incorrect 44 ms 92760 KB Output isn't correct
4 Halted 0 ms 0 KB -