Submission #341844

#	Time	Username	Problem	Language	Result	Execution time	Memory
341844		Redhood	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1039 ms	88432 KiB

sortbooks

#include<bits/stdc++.h>
#define fi first
#define se second
#define len(x) (int)(x).size()
#define pb push_back
#define p2(x) (x)*(x)
#define all(x) (x).begin() , (x).end()
#define mkp make_pair


//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long double ld;
typedef long long ll;
const int N = 1e6 + 10;
const int inf = 1e9;
int fen[N];
void add(int v , int mn){
    for(;v<N;v += v & -v)
        fen[v] = max(fen[v] , mn);
}
int get(int r){
    int ans = -inf;
    for(;r > 0 ; r -= r & -r)
        ans = max(ans , fen[r]);
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n , m;cin >> n >> m;
    vector < int > w(n);
    for(auto &i  : w)
        cin >> i;
    vector < int > answer(m) , K(m);
    vector < vector < pair < int , int > > > left(n + 1);


    for(int qq = 0; qq < m; ++qq){
        int l , r , k;
        cin >> l >> r >> k;
        --l , --r;
        K[qq] = k;
        left[l].pb({qq , r});
    }
    vector < int > stac;
    fill(fen , fen + N , -inf);
    for(int l = n - 1; l  >= 0 ;--l){
        while(!stac.empty() && w[stac.back()] < w[l]){
            int lul = stac.back();
            add(lul , w[l]+w[stac.back()]);
            stac.pop_back();
        }
        stac.pb(l);
        for(auto u : left[l]){
            answer[u.fi] = get(u.se);
        }
    }
//    cout << " ANSWER \n";
//    for(auto u : answer)
//        cout << u << '\n';
    for(int i = 0 ; i < m; ++i){
        if(K[i] >= answer[i])
            cout << 1;
        else
            cout << 0;
        cout << '\n';
    }
    return 0;
}
/*


*/

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