답안 #979797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979797	2024-05-11T11:29:13 Z	asdasdqwer	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1481 ms	116556 KB

sortbooks

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define tii array<int,3>

struct Query {
    int l, r, k;
    int idx;

    bool operator<(const Query &q) {
        if (q.r != r) return r < q.r;
        return l < q.l;
    }
};

struct Segtree {
    int n;
    vector<int> seg, lz;

    Segtree(int sz) {
        n=1;
        while (n<sz)n*=2;
        seg.assign(2*n,0);
        lz.assign(2*n,0);
    }

    void pushdown(int x) {
        if (lz[x] == 0) return;
        lz[2*x+1] = lz[2*x+2] = seg[2*x+1] = seg[2*x+2] = lz[x];
        lz[x] = 0;
    }

    void set(int l, int r, int v, int x, int lx, int rx) {
        if (lx >= r || rx <= l) return;
        if (lx >= l && rx <= r) {
            seg[x] = lz[x] = v;
            return;
        }
        pushdown(x);
        int m=(lx+rx)/2;
        set(l, r, v, 2*x+1, lx, m);
        set(l, r, v, 2*x+2, m, rx);
    }

    void set(int l, int r, int v) {
        set(l, r, v, 0, 0, n);
    }

    int get(int i, int x, int lx, int rx) {
        if (rx-lx==1) {
            return seg[x];
        }
        pushdown(x);
        int m=(lx+rx)/2;
        if (i<m)return get(i,2*x+1,lx,m);
        return get(i, 2*x+2, m, rx);
    }

    int get(int i) {
        return get(i, 0, 0, n);
    }
};

signed main() {
    int n,m;cin>>n>>m;
    vector<int> a(n);
    for (auto &x:a) cin>>x;

    vector<Query> q;
    vector<bool> ans(m, false);
    for (int i=0;i<m;i++) {
        Query qq;
        qq.idx = i;
        cin>>qq.l>>qq.r>>qq.k;
        qq.l--;qq.r--;
        if (qq.l == qq.r) {
            ans[i] = true;
            continue;
        }

        q.push_back(qq);
    }

    sort(q.begin(), q.end());
    int pt = 0;
    stack<tii> s;

    Segtree sg(n);

    vector<int> ans2(m);

    for (int i=1;i<n;i++) {
        if (a[i] < a[i-1]) {
            while (s.size() && s.top()[2] <= a[i-1]) {
                s.pop();
            }

            int last;
            if (s.size()) {
                last = s.top()[1] + 1;
            }
            else {
                last = 0;
            }

            s.push({last, i-1, a[i-1]});
            sg.set(last, i, a[i-1]);
        }

        while (pt < (int)q.size() && q[pt].r == i) {
            int qt = q[pt].l;
            int val = sg.get(qt);
            ans[q[pt].idx] = (q[pt].k >= val);
            ans2[q[pt].idx] = val;
            pt++;
        }
    }

    for (int i=0;i<m;i++) {
        cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 9.0

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

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1481 ms	114160 KB	Output is correct
2	Correct	1402 ms	115416 KB	Output is correct
3	Correct	1381 ms	116556 KB	Output is correct
4	Correct	1435 ms	115812 KB	Output is correct
5	Correct	1356 ms	116020 KB	Output is correct