Submission #162952

#	Time	Username	Problem	Language	Result	Execution time	Memory
162952		dandrozavr	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2860 ms	27544 KiB

sortbooks

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/   /▐/   /▌/ /▀/ /░/ /🔥/   choose  own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/



//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>

using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>'
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;

#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
#define fi first
#define se second
//#define pi 3.14159265358979323846
#define pii pair < ll , int >
#define pipii pair< int, pair < int , int > >
#define siz(n) (int)(n.size())


const int inf=1e9 + 7;
const ll inf18=1e18 + 7;
const int N=1e6 + 7;
const int MN = 2097152;
int t[MN + 5], need[MN + 5], a[N], otv[N], sqr, al;
vector < int > b[1005];

int solve(int l, int r)
{
    int vl = l / sqr, vr = r / sqr;

    if (vl == vr)
    {
        int ans = 0;
        int mx = 0;
        for (int i = l; i <= r; ++i)
        {
            if (mx > a[i])
                ans = max(ans, mx + a[i]); else
                mx = a[i];
        }
        return ans;
    }
    int sl = (vl + 1) * sqr;
    int ans = 0, mx = 0;

    for (int i = l; i < sl; ++i)
    {
        if (mx > a[i])
            ans = max(ans, mx + a[i]); else
            mx = a[i];
    }
    for (int bl = vl + 1; bl < vr; ++bl)
    {
        ans = max(ans, otv[bl]);
        int poz = lower_bound(b[bl].begin(), b[bl].end(), mx) - b[bl].begin();
        if (poz)
        {
            --poz;
            ans = max(ans, b[bl][poz] + mx);
        }

        if (b[bl].back() > mx) mx = b[bl].back();
    }

    for (int i = vr * sqr; i <= r; ++i)
    {
        if (mx > a[i])
            ans = max(ans, mx + a[i]); else
            mx = a[i];
    }

    return ans;
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifdef Estb_probitie
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int n, m;
    cin >> n >> m;

    if (n > 2e5 || m > 2e5)
    {
        int a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        int now = 1e9;
        int nxt[n];

        for (int i = n - 1; i >= 0; --i)
        {
            if (i + 1 < n && a[i] > a[i + 1])
                now = i;
            nxt[i] = now;
        }
        for (int i = 0; i < m; ++i)
        {
            int l, r, k;
            cin >> l >> r >> k;
            --l, --r;
            if (nxt[l] >= r)
                cout << "1\n"; else cout << "0\n";
        }


    }

    sqr = sqrt(n);
    int nxt = sqr;
    int now = 0, mx = 0;

    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];

        if (i == nxt)
        {
            ++now;
            nxt += sqr;
            mx = 0;
        }

        b[now].pb(a[i]);
        if (mx > a[i])
            otv[now] = max(otv[now], mx + a[i]); else
            mx = a[i];
    }

    for (int i = 0; i < 1000; ++i)
        sort(b[i].begin(),b[i].end());

    for (int i = 0; i < m; ++i)
    {
        int l, r, k;
        cin >> l >> r >> k;
        --l, --r;
        int ans = solve(l, r);
        if (ans > k)
            cout << 0 << '\n'; else cout << 1 << '\n';
    }

}

Compilation message (stderr)

sortbooks.cpp:35:50: warning: missing terminating ' character
 #include <ext/pb_ds/detail/standard_policies.hpp>'
                                                  ^
sortbooks.cpp:35:50: warning: extra tokens at end of #include directive

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