oj.uz

답안 #861717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861717 2023-10-16T17:52:07 Z Dec0Dedd Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 1702 ms 149208 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 1e6+10;
const int INF = 1e9+100;

int w[N], k[N], lf[N], x[N], n, q;
vector<pii> v[N];
vector<int> evs[N];

struct segtree {
    vector<int> t;

    void init(int k) {
        int sz=1;
        while (sz < 4*k) sz*=2;
        t.resize(sz);
    }

    void upd(int v, int l, int r, int p, int val) {
        if (l == r) {
            t[v]=val;
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, val);
        else upd(2*v+1, m+1, r, p, val);
    }

    int que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return 0;
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2;
        return max(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }
};

int main() {
    cin>>n>>q;
    for (int i=1; i<=n; ++i) cin>>w[i];

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

    segtree t; t.init(n+10);

    w[0]=INF;
    stack<int> st; st.push(0);
    for (int i=1; i<=n; ++i) {
        while (w[st.top()] <= w[i]) st.pop();
        lf[i]=st.top(); evs[st.top()].push_back(i);
        if (lf[i] > 0) t.upd(1, 1, n, i, w[st.top()]+w[i]);
        st.push(i);
    }

    for (int i=1; i<=n; ++i) {
        for (auto u : v[i]) x[u.second]=t.que(1, 1, n, i, u.first);
        for (auto u : evs[i]) t.upd(1, 1, n, u, 0);
    }

    for (int i=1; i<=q; ++i) {
        if (x[i] > k[i]) cout<<0<<"\n";
        else cout<<1<<"\n";
    }
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 53852 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Incorrect 12 ms 53984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 53852 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Incorrect 12 ms 53984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 53852 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Incorrect 12 ms 53984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 53852 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Incorrect 12 ms 53984 KB Output isn't correct
4 Halted 0 ms 0 KB -