oj.uz

Submission #151673

# Submission time Handle Problem Language Result Execution time Memory
151673 2019-09-04T05:32:19 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 30016 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)

using namespace std;
typedef long double ld;
const int MAXN = 1123456;
const int N = 1e6 + 200;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

template <typename T> void vout(T s){cout << s << endl;exit(0);}
pair<pair<int, int>, int> b[N];
pair<int, int> v[N];
int t[4 * N],a[N],n,Q,limit,l,r,x,ans[N],q[N],step;
int pos, val;
void upd(int v,int tl,int tr)
{
    if(tl == tr)
    {
        t[v] = val + a[tl];
        return;
    }
    int tm = (tl + tr) >> 1;
    if(pos <= tm) upd(v << 1, tl, tm);
    else upd(v << 1 | 1, tm + 1, tr);
    t[v] = max(t[v << 1], t[v << 1 | 1]);
}
int get(int v,int tl,int tr)
{
    if(tr < l || tl > r) return 0;
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return max(get(v << 1, tl, tm), get(v << 1 | 1, tm + 1, tr));
}
void make(int l,int r)
{
    int x,Pos;
    for(int i = r; i >= l; i--)
    {
        x = a[i];
        while(step > 0 && x > v[step].fi)
        {
            Pos = v[step].se;
            pos = Pos;
            val = x;
            upd(1, 1, n);
            step--;
        }
        v[++step] = {x, i};
    }
}
bool comp(int i,int j)
{
    return (b[i].fi.fi > b[j].fi.fi) || (b[i].fi.fi == b[j].fi.fi && (m_p(b[i].fi.se, b[i].se) < m_p(b[j].fi.se, b[j].se)));
}
int main()
{
    ios_base::sync_with_stdio();cin.tie(0);cout.tie(0);
    cin>>n>>Q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    limit = n;
    for(int i = 1; i <= Q; i++)
    {
        cin>>l>>r>>x;
        b[i] = {{l, r}, x};
        q[i] = i;
    }
    stable_sort(q + 1, q + Q + 1, comp);
    for(int i,j = 1; j <= Q; j++)
    {
        i = q[j];
        l = b[i].fi.fi;
        r = b[i].fi.se;
        if(limit >= l)
        {
            make(l, limit);
            limit = l - 1;
        }
        x = get(1, 1, n);
        ans[i] = (x <= b[i].se);
    }
    for(int i = 1; i <= Q; i++) cout<<ans[i]<<"\n";
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3015 ms 30016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 3944 KB Output is correct
2 Correct 229 ms 3896 KB Output is correct
3 Correct 225 ms 3644 KB Output is correct
4 Correct 228 ms 3752 KB Output is correct
5 Correct 225 ms 3640 KB Output is correct
6 Correct 212 ms 3796 KB Output is correct
7 Correct 212 ms 3788 KB Output is correct
8 Correct 202 ms 4012 KB Output is correct
9 Correct 146 ms 2620 KB Output is correct
10 Correct 198 ms 3944 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 380 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 11 ms 508 KB Output is correct
13 Correct 12 ms 508 KB Output is correct
14 Correct 16 ms 632 KB Output is correct
15 Correct 16 ms 504 KB Output is correct
16 Correct 13 ms 504 KB Output is correct
17 Correct 12 ms 504 KB Output is correct
18 Correct 11 ms 504 KB Output is correct
19 Correct 657 ms 7532 KB Output is correct
20 Correct 649 ms 7628 KB Output is correct
21 Correct 627 ms 7508 KB Output is correct
22 Correct 629 ms 7692 KB Output is correct
23 Correct 621 ms 7556 KB Output is correct
24 Correct 591 ms 7080 KB Output is correct
25 Correct 594 ms 7268 KB Output is correct
26 Correct 609 ms 7052 KB Output is correct
27 Correct 611 ms 7008 KB Output is correct
28 Correct 622 ms 7140 KB Output is correct
29 Correct 630 ms 7000 KB Output is correct
30 Correct 627 ms 7016 KB Output is correct
31 Correct 611 ms 7008 KB Output is correct
32 Correct 619 ms 7140 KB Output is correct
33 Correct 617 ms 6976 KB Output is correct
34 Correct 612 ms 7176 KB Output is correct
35 Correct 610 ms 7072 KB Output is correct
36 Correct 573 ms 7000 KB Output is correct
37 Correct 576 ms 7036 KB Output is correct
38 Correct 607 ms 7140 KB Output is correct
39 Correct 524 ms 7304 KB Output is correct
40 Correct 442 ms 6352 KB Output is correct
41 Correct 492 ms 7396 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 380 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 9 ms 504 KB Output is correct
12 Correct 11 ms 508 KB Output is correct
13 Correct 12 ms 508 KB Output is correct
14 Correct 16 ms 632 KB Output is correct
15 Correct 16 ms 504 KB Output is correct
16 Correct 13 ms 504 KB Output is correct
17 Correct 12 ms 504 KB Output is correct
18 Correct 11 ms 504 KB Output is correct
19 Execution timed out 3015 ms 30016 KB Time limit exceeded
20 Halted 0 ms 0 KB -