oj.uz

Submission #151707

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

#define fi first
#define se second

using namespace std;
const int N = 4e6 + 200;

pair<int, int> v[N],b[N];
vector<int> q[N];
int t[4 * N],a[N],n,Q,limit,l,r,x,step,pos,val;
bool ans[N];
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};
    }
}
int main()
{
    ios_base::sync_with_stdio();cin.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] = {r, x};
        q[l].push_back(i);
    }
    for(int j = n; j > 0; j--) if(!q[j].empty())
        for(auto i : q[j])
        {
            l = j;
            r = b[i].fi;
            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]<<endl;
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94332 KB Output is correct
2 Correct 89 ms 94320 KB Output is correct
3 Correct 95 ms 94280 KB Output is correct
4 Correct 91 ms 94380 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 103 ms 94428 KB Output is correct
7 Correct 107 ms 94328 KB Output is correct
8 Correct 90 ms 94276 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 104 ms 94328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94332 KB Output is correct
2 Correct 89 ms 94320 KB Output is correct
3 Correct 95 ms 94280 KB Output is correct
4 Correct 91 ms 94380 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 103 ms 94428 KB Output is correct
7 Correct 107 ms 94328 KB Output is correct
8 Correct 90 ms 94276 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 104 ms 94328 KB Output is correct
11 Correct 105 ms 94308 KB Output is correct
12 Correct 103 ms 94456 KB Output is correct
13 Correct 106 ms 94456 KB Output is correct
14 Correct 115 ms 94628 KB Output is correct
15 Correct 116 ms 94520 KB Output is correct
16 Correct 111 ms 94460 KB Output is correct
17 Correct 111 ms 94500 KB Output is correct
18 Correct 111 ms 94456 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 98856 KB Output is correct
2 Correct 601 ms 97760 KB Output is correct
3 Correct 590 ms 98340 KB Output is correct
4 Correct 590 ms 98632 KB Output is correct
5 Correct 589 ms 98484 KB Output is correct
6 Correct 557 ms 97144 KB Output is correct
7 Correct 557 ms 97400 KB Output is correct
8 Correct 560 ms 98164 KB Output is correct
9 Correct 487 ms 95996 KB Output is correct
10 Correct 556 ms 98288 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94332 KB Output is correct
2 Correct 89 ms 94320 KB Output is correct
3 Correct 95 ms 94280 KB Output is correct
4 Correct 91 ms 94380 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 103 ms 94428 KB Output is correct
7 Correct 107 ms 94328 KB Output is correct
8 Correct 90 ms 94276 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 104 ms 94328 KB Output is correct
11 Correct 105 ms 94308 KB Output is correct
12 Correct 103 ms 94456 KB Output is correct
13 Correct 106 ms 94456 KB Output is correct
14 Correct 115 ms 94628 KB Output is correct
15 Correct 116 ms 94520 KB Output is correct
16 Correct 111 ms 94460 KB Output is correct
17 Correct 111 ms 94500 KB Output is correct
18 Correct 111 ms 94456 KB Output is correct
19 Correct 1355 ms 103320 KB Output is correct
20 Correct 1320 ms 103320 KB Output is correct
21 Correct 1285 ms 101068 KB Output is correct
22 Correct 1316 ms 100968 KB Output is correct
23 Correct 1328 ms 101068 KB Output is correct
24 Correct 1197 ms 100560 KB Output is correct
25 Correct 1182 ms 100480 KB Output is correct
26 Correct 1273 ms 101240 KB Output is correct
27 Correct 1239 ms 101396 KB Output is correct
28 Correct 1242 ms 101580 KB Output is correct
29 Correct 1313 ms 102844 KB Output is correct
30 Correct 1276 ms 102832 KB Output is correct
31 Correct 1263 ms 102904 KB Output is correct
32 Correct 1278 ms 102736 KB Output is correct
33 Correct 1288 ms 102804 KB Output is correct
34 Correct 1165 ms 99920 KB Output is correct
35 Correct 1167 ms 100144 KB Output is correct
36 Correct 1153 ms 100096 KB Output is correct
37 Correct 1174 ms 99960 KB Output is correct
38 Correct 1163 ms 99992 KB Output is correct
39 Correct 1145 ms 101624 KB Output is correct
40 Correct 1070 ms 100368 KB Output is correct
41 Correct 1157 ms 101728 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94332 KB Output is correct
2 Correct 89 ms 94320 KB Output is correct
3 Correct 95 ms 94280 KB Output is correct
4 Correct 91 ms 94380 KB Output is correct
5 Correct 89 ms 94328 KB Output is correct
6 Correct 103 ms 94428 KB Output is correct
7 Correct 107 ms 94328 KB Output is correct
8 Correct 90 ms 94276 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 104 ms 94328 KB Output is correct
11 Correct 105 ms 94308 KB Output is correct
12 Correct 103 ms 94456 KB Output is correct
13 Correct 106 ms 94456 KB Output is correct
14 Correct 115 ms 94628 KB Output is correct
15 Correct 116 ms 94520 KB Output is correct
16 Correct 111 ms 94460 KB Output is correct
17 Correct 111 ms 94500 KB Output is correct
18 Correct 111 ms 94456 KB Output is correct
19 Execution timed out 3056 ms 129600 KB Time limit exceeded
20 Halted 0 ms 0 KB -