oj.uz

Submission #151708

# Submission time Handle Problem Language Result Execution time Memory
151708 2019-09-04T08:34:14 Z leatherman Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 128948 KB 
#include <iostream>
#include<vector>

#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 87 ms 94328 KB Output is correct
2 Correct 89 ms 94316 KB Output is correct
3 Correct 90 ms 94328 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 88 ms 94328 KB Output is correct
6 Correct 90 ms 94244 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94328 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 89 ms 94316 KB Output is correct
3 Correct 90 ms 94328 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 88 ms 94328 KB Output is correct
6 Correct 90 ms 94244 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94328 KB Output is correct
11 Correct 102 ms 94360 KB Output is correct
12 Correct 104 ms 94508 KB Output is correct
13 Correct 106 ms 94512 KB Output is correct
14 Correct 116 ms 94584 KB Output is correct
15 Correct 115 ms 94456 KB Output is correct
16 Correct 113 ms 94556 KB Output is correct
17 Correct 110 ms 94456 KB Output is correct
18 Correct 112 ms 94584 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 98900 KB Output is correct
2 Correct 591 ms 97912 KB Output is correct
3 Correct 602 ms 98200 KB Output is correct
4 Correct 610 ms 98552 KB Output is correct
5 Correct 605 ms 98620 KB Output is correct
6 Correct 556 ms 97264 KB Output is correct
7 Correct 557 ms 97376 KB Output is correct
8 Correct 561 ms 98200 KB Output is correct
9 Correct 490 ms 96052 KB Output is correct
10 Correct 567 ms 98196 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 89 ms 94316 KB Output is correct
3 Correct 90 ms 94328 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 88 ms 94328 KB Output is correct
6 Correct 90 ms 94244 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94328 KB Output is correct
11 Correct 102 ms 94360 KB Output is correct
12 Correct 104 ms 94508 KB Output is correct
13 Correct 106 ms 94512 KB Output is correct
14 Correct 116 ms 94584 KB Output is correct
15 Correct 115 ms 94456 KB Output is correct
16 Correct 113 ms 94556 KB Output is correct
17 Correct 110 ms 94456 KB Output is correct
18 Correct 112 ms 94584 KB Output is correct
19 Correct 1330 ms 103220 KB Output is correct
20 Correct 1323 ms 103360 KB Output is correct
21 Correct 1273 ms 100972 KB Output is correct
22 Correct 1258 ms 101048 KB Output is correct
23 Correct 1261 ms 101080 KB Output is correct
24 Correct 1231 ms 100240 KB Output is correct
25 Correct 1206 ms 100388 KB Output is correct
26 Correct 1272 ms 101368 KB Output is correct
27 Correct 1256 ms 101272 KB Output is correct
28 Correct 1265 ms 101696 KB Output is correct
29 Correct 1306 ms 102700 KB Output is correct
30 Correct 1273 ms 103136 KB Output is correct
31 Correct 1272 ms 102912 KB Output is correct
32 Correct 1294 ms 102612 KB Output is correct
33 Correct 1278 ms 102796 KB Output is correct
34 Correct 1190 ms 99944 KB Output is correct
35 Correct 1216 ms 99988 KB Output is correct
36 Correct 1183 ms 100116 KB Output is correct
37 Correct 1179 ms 100140 KB Output is correct
38 Correct 1181 ms 100040 KB Output is correct
39 Correct 1173 ms 101732 KB Output is correct
40 Correct 1085 ms 100440 KB Output is correct
41 Correct 1147 ms 101804 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 94328 KB Output is correct
2 Correct 89 ms 94316 KB Output is correct
3 Correct 90 ms 94328 KB Output is correct
4 Correct 88 ms 94328 KB Output is correct
5 Correct 88 ms 94328 KB Output is correct
6 Correct 90 ms 94244 KB Output is correct
7 Correct 91 ms 94328 KB Output is correct
8 Correct 90 ms 94328 KB Output is correct
9 Correct 90 ms 94328 KB Output is correct
10 Correct 90 ms 94328 KB Output is correct
11 Correct 102 ms 94360 KB Output is correct
12 Correct 104 ms 94508 KB Output is correct
13 Correct 106 ms 94512 KB Output is correct
14 Correct 116 ms 94584 KB Output is correct
15 Correct 115 ms 94456 KB Output is correct
16 Correct 113 ms 94556 KB Output is correct
17 Correct 110 ms 94456 KB Output is correct
18 Correct 112 ms 94584 KB Output is correct
19 Execution timed out 3060 ms 128948 KB Time limit exceeded
20 Halted 0 ms 0 KB -