답안 #371083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371083	2021-02-25T18:40:37 Z	nicolaalexandra	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2625 ms	67632 KB

sortbooks

#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;

struct query{
    int x,val,poz;
};
vector <query> qry[DIM];

int v[DIM],aint[DIM*4],ans[DIM];
deque <int> d;
int n,m,i,sol,x,y,val;


void update (int nod, int st, int dr, int poz, int val){
    if (st == dr){
        aint[nod] = max (aint[nod],val);
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,val);
    else update ((nod<<1)|1,mid+1,dr,poz,val);

    aint[nod] = max (aint[nod<<1],aint[(nod<<1)|1]);
}

void query (int nod, int st, int dr, int x, int y){
    if (x <= st && dr <= y){
        sol = max (sol,aint[nod]);
        return;
    }
    int mid = (st+dr)>>1;
    if (x <= mid)
        query (nod<<1,st,mid,x,y);
    if (y > mid)
        query ((nod<<1)|1,mid+1,dr,x,y);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>v[i];

    for (i=1;i<=m;i++){
        cin>>x>>y>>val;
        qry[y].push_back({x,val,i});
        ans[i] = 1;
    }

    for (i=1;i<=n;i++){
        while (!d.empty() && v[i] >= v[d.back()])
            d.pop_back();

        if (!d.empty())
            update (1,1,n,d.back(),v[i] + v[d.back()]);

        d.push_back(i);

        for (auto it : qry[i]){
            sol = 0;
            query (1,1,n,it.x,i);
            if (sol > it.val)
                ans[it.poz] = 0;
        }
    }

    for (i=1;i<=m;i++)
        cout<<ans[i]<<"\n";

    return 0;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	16 ms	23788 KB	Output is correct
3	Correct	17 ms	23788 KB	Output is correct
4	Correct	16 ms	23788 KB	Output is correct
5	Correct	17 ms	23788 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	20 ms	23788 KB	Output is correct
8	Correct	17 ms	23788 KB	Output is correct
9	Correct	17 ms	23788 KB	Output is correct
10	Correct	17 ms	23788 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	16 ms	23788 KB	Output is correct
3	Correct	17 ms	23788 KB	Output is correct
4	Correct	16 ms	23788 KB	Output is correct
5	Correct	17 ms	23788 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	20 ms	23788 KB	Output is correct
8	Correct	17 ms	23788 KB	Output is correct
9	Correct	17 ms	23788 KB	Output is correct
10	Correct	17 ms	23788 KB	Output is correct
11	Correct	21 ms	23916 KB	Output is correct
12	Correct	23 ms	24044 KB	Output is correct
13	Correct	23 ms	24044 KB	Output is correct
14	Correct	25 ms	24044 KB	Output is correct
15	Correct	30 ms	24044 KB	Output is correct
16	Correct	24 ms	24044 KB	Output is correct
17	Correct	23 ms	24044 KB	Output is correct
18	Correct	23 ms	24044 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2548 ms	63756 KB	Output is correct
2	Correct	2587 ms	67528 KB	Output is correct
3	Correct	2572 ms	67436 KB	Output is correct
4	Correct	2561 ms	67632 KB	Output is correct
5	Correct	2251 ms	59512 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	189 ms	28012 KB	Output is correct
2	Correct	192 ms	27756 KB	Output is correct
3	Correct	168 ms	26860 KB	Output is correct
4	Correct	167 ms	26860 KB	Output is correct
5	Correct	178 ms	26960 KB	Output is correct
6	Correct	154 ms	26688 KB	Output is correct
7	Correct	154 ms	26604 KB	Output is correct
8	Correct	155 ms	26920 KB	Output is correct
9	Correct	105 ms	25912 KB	Output is correct
10	Correct	158 ms	26920 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	16 ms	23788 KB	Output is correct
3	Correct	17 ms	23788 KB	Output is correct
4	Correct	16 ms	23788 KB	Output is correct
5	Correct	17 ms	23788 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	20 ms	23788 KB	Output is correct
8	Correct	17 ms	23788 KB	Output is correct
9	Correct	17 ms	23788 KB	Output is correct
10	Correct	17 ms	23788 KB	Output is correct
11	Correct	21 ms	23916 KB	Output is correct
12	Correct	23 ms	24044 KB	Output is correct
13	Correct	23 ms	24044 KB	Output is correct
14	Correct	25 ms	24044 KB	Output is correct
15	Correct	30 ms	24044 KB	Output is correct
16	Correct	24 ms	24044 KB	Output is correct
17	Correct	23 ms	24044 KB	Output is correct
18	Correct	23 ms	24044 KB	Output is correct
19	Correct	484 ms	36544 KB	Output is correct
20	Correct	484 ms	38636 KB	Output is correct
21	Correct	435 ms	38124 KB	Output is correct
22	Correct	438 ms	37996 KB	Output is correct
23	Correct	426 ms	38124 KB	Output is correct
24	Correct	382 ms	35820 KB	Output is correct
25	Correct	397 ms	35820 KB	Output is correct
26	Correct	409 ms	36332 KB	Output is correct
27	Correct	415 ms	36204 KB	Output is correct
28	Correct	410 ms	36332 KB	Output is correct
29	Correct	431 ms	36720 KB	Output is correct
30	Correct	422 ms	36588 KB	Output is correct
31	Correct	427 ms	36588 KB	Output is correct
32	Correct	428 ms	36716 KB	Output is correct
33	Correct	432 ms	36728 KB	Output is correct
34	Correct	372 ms	35564 KB	Output is correct
35	Correct	370 ms	35436 KB	Output is correct
36	Correct	367 ms	35308 KB	Output is correct
37	Correct	366 ms	35180 KB	Output is correct
38	Correct	375 ms	35376 KB	Output is correct
39	Correct	369 ms	35748 KB	Output is correct
40	Correct	311 ms	33696 KB	Output is correct
41	Correct	356 ms	34724 KB	Output is correct

Subtask #6
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	23788 KB	Output is correct
2	Correct	16 ms	23788 KB	Output is correct
3	Correct	17 ms	23788 KB	Output is correct
4	Correct	16 ms	23788 KB	Output is correct
5	Correct	17 ms	23788 KB	Output is correct
6	Correct	17 ms	23916 KB	Output is correct
7	Correct	20 ms	23788 KB	Output is correct
8	Correct	17 ms	23788 KB	Output is correct
9	Correct	17 ms	23788 KB	Output is correct
10	Correct	17 ms	23788 KB	Output is correct
11	Correct	21 ms	23916 KB	Output is correct
12	Correct	23 ms	24044 KB	Output is correct
13	Correct	23 ms	24044 KB	Output is correct
14	Correct	25 ms	24044 KB	Output is correct
15	Correct	30 ms	24044 KB	Output is correct
16	Correct	24 ms	24044 KB	Output is correct
17	Correct	23 ms	24044 KB	Output is correct
18	Correct	23 ms	24044 KB	Output is correct
19	Correct	2548 ms	63756 KB	Output is correct
20	Correct	2587 ms	67528 KB	Output is correct
21	Correct	2572 ms	67436 KB	Output is correct
22	Correct	2561 ms	67632 KB	Output is correct
23	Correct	2251 ms	59512 KB	Output is correct
24	Correct	189 ms	28012 KB	Output is correct
25	Correct	192 ms	27756 KB	Output is correct
26	Correct	168 ms	26860 KB	Output is correct
27	Correct	167 ms	26860 KB	Output is correct
28	Correct	178 ms	26960 KB	Output is correct
29	Correct	154 ms	26688 KB	Output is correct
30	Correct	154 ms	26604 KB	Output is correct
31	Correct	155 ms	26920 KB	Output is correct
32	Correct	105 ms	25912 KB	Output is correct
33	Correct	158 ms	26920 KB	Output is correct
34	Correct	484 ms	36544 KB	Output is correct
35	Correct	484 ms	38636 KB	Output is correct
36	Correct	435 ms	38124 KB	Output is correct
37	Correct	438 ms	37996 KB	Output is correct
38	Correct	426 ms	38124 KB	Output is correct
39	Correct	382 ms	35820 KB	Output is correct
40	Correct	397 ms	35820 KB	Output is correct
41	Correct	409 ms	36332 KB	Output is correct
42	Correct	415 ms	36204 KB	Output is correct
43	Correct	410 ms	36332 KB	Output is correct
44	Correct	431 ms	36720 KB	Output is correct
45	Correct	422 ms	36588 KB	Output is correct
46	Correct	427 ms	36588 KB	Output is correct
47	Correct	428 ms	36716 KB	Output is correct
48	Correct	432 ms	36728 KB	Output is correct
49	Correct	372 ms	35564 KB	Output is correct
50	Correct	370 ms	35436 KB	Output is correct
51	Correct	367 ms	35308 KB	Output is correct
52	Correct	366 ms	35180 KB	Output is correct
53	Correct	375 ms	35376 KB	Output is correct
54	Correct	369 ms	35748 KB	Output is correct
55	Correct	311 ms	33696 KB	Output is correct
56	Correct	356 ms	34724 KB	Output is correct
57	Correct	2625 ms	67212 KB	Output is correct
58	Correct	2548 ms	67132 KB	Output is correct
59	Correct	2496 ms	65572 KB	Output is correct
60	Correct	2501 ms	65644 KB	Output is correct
61	Correct	2430 ms	65644 KB	Output is correct
62	Correct	2455 ms	65644 KB	Output is correct
63	Correct	1859 ms	55788 KB	Output is correct
64	Correct	1874 ms	55680 KB	Output is correct
65	Correct	2169 ms	57240 KB	Output is correct
66	Correct	2124 ms	57452 KB	Output is correct
67	Correct	2138 ms	57544 KB	Output is correct
68	Correct	2205 ms	59064 KB	Output is correct
69	Correct	2195 ms	59204 KB	Output is correct
70	Correct	2196 ms	58860 KB	Output is correct
71	Correct	2191 ms	58732 KB	Output is correct
72	Correct	2193 ms	58604 KB	Output is correct
73	Correct	1785 ms	53228 KB	Output is correct
74	Correct	1818 ms	53484 KB	Output is correct
75	Correct	1802 ms	53324 KB	Output is correct
76	Correct	1799 ms	53412 KB	Output is correct
77	Correct	1791 ms	52976 KB	Output is correct
78	Correct	1963 ms	59228 KB	Output is correct
79	Correct	1518 ms	52000 KB	Output is correct
80	Correct	1875 ms	56212 KB	Output is correct

답안 #371083

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 9.0 / 9.0

Subtask #3 13.0 / 13.0

Subtask #4 17.0 / 17.0

Subtask #5 30.0 / 30.0

Subtask #6 23.0 / 23.0

Subtask #1
8.0 / 8.0

Subtask #2
9.0 / 9.0

Subtask #3
13.0 / 13.0

Subtask #4
17.0 / 17.0

Subtask #5
30.0 / 30.0

Subtask #6
23.0 / 23.0