Submission #1138690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138690		AHOKA	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	506 ms	83016 KiB

sortbooks

#pragma GCC optimize("O3") 

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define double long double
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 1e6 + 10, maxm = 5e3 + 10, oo = 1e18 + 10, lg = 18, sq = 350, mod = 998244353;

int n, m, ans[maxn];

int a[maxn];

vector<ppp> q[maxn];

int fen[maxn];

void add(int i, int val){
    for (i = maxn - i - 5; i < maxn; i += i & -i)
        fen[i] = max(fen[i], val);
}
 
int get(int i){
    int res = -oo;
    for (i = maxn - i - 5; i > 0; i -= i & -i)
        res = max(fen[i], res);
    return res;
}

signed main()
{
	threesum;
    cin >> n >> m;
    for (int i = 1; i <= n;i++)
        cin >> a[i];

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

    vector<int> stk;
    for (int i = 1; i <= n; i++)
    {
        while(stk.size() && a[stk.back()] <= a[i])
            stk.pop_back();

        if(stk.size())
            add(stk.back(), a[stk.back()] + a[i]);

        stk.push_back(i);

        for(auto [l, p] : q[i]){
            auto [k, id] = p;
            ans[id] = (get(l) <= k);
        }
    }

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

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23