oj.uz

Submission #162952

# Submission time Handle Problem Language Result Execution time Memory
162952 2019-11-10T11:52:19 Z dandrozavr Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2860 ms 27544 KB 
/*
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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 448 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 448 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 8 ms 632 KB Output is correct
15 Correct 8 ms 632 KB Output is correct
16 Correct 8 ms 632 KB Output is correct
17 Correct 7 ms 504 KB Output is correct
18 Correct 8 ms 504 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2860 ms 27544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 2240 KB Output is correct
2 Correct 761 ms 2360 KB Output is correct
3 Correct 286 ms 2200 KB Output is correct
4 Correct 217 ms 2168 KB Output is correct
5 Correct 192 ms 2148 KB Output is correct
6 Correct 603 ms 2308 KB Output is correct
7 Correct 569 ms 2156 KB Output is correct
8 Correct 486 ms 2280 KB Output is correct
9 Correct 56 ms 1272 KB Output is correct
10 Correct 435 ms 2284 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 448 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 8 ms 632 KB Output is correct
15 Correct 8 ms 632 KB Output is correct
16 Correct 8 ms 632 KB Output is correct
17 Correct 7 ms 504 KB Output is correct
18 Correct 8 ms 504 KB Output is correct
19 Correct 759 ms 3416 KB Output is correct
20 Correct 748 ms 2984 KB Output is correct
21 Correct 2532 ms 2648 KB Output is correct
22 Correct 2445 ms 2592 KB Output is correct
23 Correct 2550 ms 2724 KB Output is correct
24 Correct 1927 ms 2536 KB Output is correct
25 Correct 1887 ms 2680 KB Output is correct
26 Correct 1211 ms 2536 KB Output is correct
27 Correct 1363 ms 2508 KB Output is correct
28 Correct 1054 ms 2772 KB Output is correct
29 Correct 542 ms 2572 KB Output is correct
30 Correct 543 ms 2572 KB Output is correct
31 Correct 600 ms 2520 KB Output is correct
32 Correct 600 ms 2484 KB Output is correct
33 Correct 589 ms 2460 KB Output is correct
34 Correct 1816 ms 2708 KB Output is correct
35 Correct 2171 ms 2648 KB Output is correct
36 Correct 2005 ms 2712 KB Output is correct
37 Correct 2013 ms 2772 KB Output is correct
38 Correct 2017 ms 2624 KB Output is correct
39 Correct 1333 ms 2516 KB Output is correct
40 Correct 948 ms 2196 KB Output is correct
41 Correct 1503 ms 2748 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 448 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 424 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 504 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 8 ms 632 KB Output is correct
15 Correct 8 ms 632 KB Output is correct
16 Correct 8 ms 632 KB Output is correct
17 Correct 7 ms 504 KB Output is correct
18 Correct 8 ms 504 KB Output is correct
19 Runtime error 2860 ms 27544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -