Submission #424814

#	Time	Username	Problem	Language	Result	Execution time	Memory
424814		egekabas	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1069 ms	92256 KiB

sortbooks

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, m;
int a[1000009];
vector<pair<pii, int>> q[1000009];
int bit[1000009];
void upd(int idx, int val){
    for(++idx; idx <= n; idx += idx&(-idx))
        bit[idx] = max(bit[idx], val);
}
int get(int idx){
    int ret = 0;
    for(++idx; idx > 0; idx -= idx&(-idx))
        ret = max(ret, bit[idx]);
    return ret;
}
int ans[1000009];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 0; i < n; ++i){
        int l, r, k;
        cin >> l >> r >> k;
        --l;
        --r;
        q[l].pb({{r, k}, i});
    }
    vector<int> vec;
    for(int i = n-1; i >= 0; --i){
        while(vec.size() && a[vec.back()] < a[i]){
            upd(vec.back(), a[vec.back()]+a[i]);
            vec.pop_back();
        }
        while(vec.size() && a[vec.back()] == a[i])
            vec.pop_back();
        vec.pb(i);
        for(auto u : q[i]){
            ans[u.ss] = (get(u.ff.ff) <= u.ff.ss);
        }        
    }
    for(int i = 0; i < m; ++i)
        cout << ans[i] << '\n';
}

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