Submission #992752

#	Time	Username	Problem	Language	Result	Execution time	Memory
992752		Ice_man	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1022 ms	98644 KiB

sortbooks

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <stack>
#include <vector>

#define endl '\n'
#define maxn 1000005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;


typedef pair <int, int> pii;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , ll> pil;
typedef pair <ll , int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}



int tree[maxn * 4];

void update(int node , int l , int r , int qp , int qval)
{
    if(l == r)
    {
        tree[node] = max(tree[node] , qval);
        return;
    }

    int mid = (l + r) / 2;

    if(qp <= mid)
        update(node * 2 , l , mid , qp , qval);
    else
        update(node * 2 + 1 , mid + 1 , r , qp , qval);
    tree[node] = max(tree[node * 2] , tree[node * 2 + 1]);
}


int query(int node , int l , int r , int ql , int qr)
{
    if(qr < l)
        return -INF;
    if(r < ql)
        return -INF;

    if(ql <= l && r <= qr)
        return tree[node];

    int mid = (l + r) / 2;
    return max(query(node * 2 , l , mid , ql , qr) , query(node * 2 + 1 , mid + 1, r , ql , qr));
}


int a[maxn];
int n , q;
vector <pii> qu[maxn];
int mood[maxn];

void read()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

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


stack <pii> s;
int mem[maxn];

void solve()
{
    for(int i = 1; i <= n; i++)
    {
        //cout << "in1" << endl;
        while(s.empty() == false && s.top().X <= a[i])
            s.pop();
        if(s.empty() == false)
            update(1 , 1 , n , s.top().Y , a[i] + s.top().X);
        //cout << "in2" << endl;
        s.push({a[i] , i});

        for(auto& e : qu[i])
            mem[e.Y] = query(1 , 1 , n , e.X , i);
    }

    for(int i = 1; i <= q; i++)
        if(mem[i] <= mood[i])
            cout << 1 << endl;
        else
            cout << 0 << endl;
}





int main()
{

/**#ifdef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ///startT = std::chrono::high_resolution_clock::now();

    read();
    //control
    solve();


    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