oj.uz

Submission #1113504

# Submission time Handle Problem Language Result Execution time Memory
1113504 2024-11-16T16:48:29 Z I_FloPPed21 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1531 ms 194308 KB 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n,q;
const int N=1e6+5;
long long v[N];
long long sum[4*N],lazy[4*N],seg[4*N],adaug[4*N],best[4*N],right_bound[N];
struct hedgehog
{
    long long i,r,k;
};
vector<hedgehog>query[N];
void find_bound()
{
    stack<long long>st;
    for(int i=1; i<=n; i++)
    {
        while(!st.empty()&&v[st.top()]<=v[i])
        {
            right_bound[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    while(!st.empty())
    {
        right_bound[st.top()]=n+1;
        st.pop();
    }
}
void propaga(int nod)
{
    if(lazy[nod]==0)
        return;

    adaug[nod*2]=lazy[nod];
    adaug[nod*2+1]=lazy[nod];
    lazy[nod*2]=lazy[nod];
    lazy[nod*2+1]=lazy[nod];
    best[nod*2]=(seg[nod*2]+lazy[nod]);
    best[nod*2+1]=(seg[nod*2+1]+lazy[nod]);
    lazy[nod]=0;
}
void update(int nod,int st,int dr,int l,int r,long long val)
{
    sum[nod]=seg[nod]+adaug[nod];
    if(l<=st&&dr<=r)
    {
        lazy[nod]=val;
        adaug[nod]=val;
        sum[nod]=seg[nod]+adaug[nod];
        best[nod]=sum[nod];
    }
    else if(l>dr||st>r)
        return;
    else
    {
        int mij=(st+dr)/2;
        propaga(nod);
        update(nod*2,st,mij,l,r,val);
        update(nod*2+1,mij+1,dr,l,r,val);
        best[nod]=max(best[nod*2],best[nod*2+1]);
    }
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        seg[nod]=v[st];
    }
    else
    {
        int mij=(st+dr)/2;
        build(nod*2,st,mij);
        build(nod*2+1,mij+1,dr);
        seg[nod]=max(seg[nod*2],seg[nod*2+1]);
    }
}
long long answer(int nod,int st,int dr,int l,int r)
{
    if(st>dr)
        return 0;
    if(l<=st&&dr<=r)
    {
        return best[nod];
    }
    else if(l>dr||st>r)
        return -1;
    else
    {
        propaga(nod);
        int mij=(st+dr)/2;
        return max(answer(nod*2,st,mij,l,r),answer(nod*2+1,mij+1,dr,l,r));
    }
}
void citeste()
{
    cin>>n>>q;
    for(int i=1; i<=n; i++)
        cin>>v[i];
    for(int i=1; i<=q; i++)
    {
        long long l,r,k;
        cin>>l>>r>>k;
        query[l].push_back({i,r,k});
    }
}
bool afis[N];
void rezolva()
{
    for(int i=n; i>=1; i--)
    {
        int dr=right_bound[i]-1;
        if(i+1<=dr)
        update(1,1,n,i+1,dr,v[i]);
        for (auto [x,y,z]:query[i])
        {
            afis[x]=(answer(1,1,n,i+1,y)<=z);

        }
    }
    for(int i=1; i<=q; i++)
        cout<<afis[i]<<'\n';
}

int main()
{

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    citeste();
    build(1,1,n);
    find_bound();
    rezolva();
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void rezolva()':
sortbooks.cpp:117:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  117 |         for (auto [x,y,z]:query[i])
      |                   ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 5 ms 29200 KB Output is correct
3 Correct 6 ms 33272 KB Output is correct
4 Correct 5 ms 29008 KB Output is correct
5 Correct 6 ms 33104 KB Output is correct
6 Correct 5 ms 33104 KB Output is correct
7 Correct 6 ms 29264 KB Output is correct
8 Correct 11 ms 24712 KB Output is correct
9 Correct 7 ms 24656 KB Output is correct
10 Correct 8 ms 24656 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 5 ms 29200 KB Output is correct
3 Correct 6 ms 33272 KB Output is correct
4 Correct 5 ms 29008 KB Output is correct
5 Correct 6 ms 33104 KB Output is correct
6 Correct 5 ms 33104 KB Output is correct
7 Correct 6 ms 29264 KB Output is correct
8 Correct 11 ms 24712 KB Output is correct
9 Correct 7 ms 24656 KB Output is correct
10 Correct 8 ms 24656 KB Output is correct
11 Correct 12 ms 25168 KB Output is correct
12 Correct 13 ms 25680 KB Output is correct
13 Correct 13 ms 25648 KB Output is correct
14 Correct 10 ms 27984 KB Output is correct
15 Correct 14 ms 25680 KB Output is correct
16 Correct 13 ms 25424 KB Output is correct
17 Correct 11 ms 25144 KB Output is correct
18 Correct 9 ms 29776 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 159048 KB Output is correct
2 Correct 1452 ms 159304 KB Output is correct
3 Correct 1438 ms 157064 KB Output is correct
4 Correct 1426 ms 159296 KB Output is correct
5 Correct 973 ms 91464 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 40128 KB Output is correct
2 Correct 91 ms 44360 KB Output is correct
3 Correct 78 ms 34060 KB Output is correct
4 Correct 81 ms 33868 KB Output is correct
5 Correct 83 ms 33864 KB Output is correct
6 Correct 61 ms 33916 KB Output is correct
7 Correct 68 ms 33864 KB Output is correct
8 Correct 92 ms 38140 KB Output is correct
9 Correct 36 ms 31556 KB Output is correct
10 Correct 67 ms 37016 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 5 ms 29200 KB Output is correct
3 Correct 6 ms 33272 KB Output is correct
4 Correct 5 ms 29008 KB Output is correct
5 Correct 6 ms 33104 KB Output is correct
6 Correct 5 ms 33104 KB Output is correct
7 Correct 6 ms 29264 KB Output is correct
8 Correct 11 ms 24712 KB Output is correct
9 Correct 7 ms 24656 KB Output is correct
10 Correct 8 ms 24656 KB Output is correct
11 Correct 12 ms 25168 KB Output is correct
12 Correct 13 ms 25680 KB Output is correct
13 Correct 13 ms 25648 KB Output is correct
14 Correct 10 ms 27984 KB Output is correct
15 Correct 14 ms 25680 KB Output is correct
16 Correct 13 ms 25424 KB Output is correct
17 Correct 11 ms 25144 KB Output is correct
18 Correct 9 ms 29776 KB Output is correct
19 Correct 215 ms 63816 KB Output is correct
20 Correct 231 ms 62024 KB Output is correct
21 Correct 196 ms 62792 KB Output is correct
22 Correct 197 ms 62932 KB Output is correct
23 Correct 194 ms 62792 KB Output is correct
24 Correct 173 ms 46556 KB Output is correct
25 Correct 146 ms 46408 KB Output is correct
26 Correct 172 ms 46152 KB Output is correct
27 Correct 154 ms 48456 KB Output is correct
28 Correct 207 ms 48712 KB Output is correct
29 Correct 190 ms 45528 KB Output is correct
30 Correct 239 ms 51016 KB Output is correct
31 Correct 200 ms 50924 KB Output is correct
32 Correct 189 ms 45640 KB Output is correct
33 Correct 212 ms 45640 KB Output is correct
34 Correct 141 ms 45440 KB Output is correct
35 Correct 138 ms 45552 KB Output is correct
36 Correct 147 ms 45392 KB Output is correct
37 Correct 164 ms 45384 KB Output is correct
38 Correct 137 ms 45388 KB Output is correct
39 Correct 161 ms 49404 KB Output is correct
40 Correct 140 ms 40948 KB Output is correct
41 Correct 158 ms 50416 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 33104 KB Output is correct
2 Correct 5 ms 29200 KB Output is correct
3 Correct 6 ms 33272 KB Output is correct
4 Correct 5 ms 29008 KB Output is correct
5 Correct 6 ms 33104 KB Output is correct
6 Correct 5 ms 33104 KB Output is correct
7 Correct 6 ms 29264 KB Output is correct
8 Correct 11 ms 24712 KB Output is correct
9 Correct 7 ms 24656 KB Output is correct
10 Correct 8 ms 24656 KB Output is correct
11 Correct 12 ms 25168 KB Output is correct
12 Correct 13 ms 25680 KB Output is correct
13 Correct 13 ms 25648 KB Output is correct
14 Correct 10 ms 27984 KB Output is correct
15 Correct 14 ms 25680 KB Output is correct
16 Correct 13 ms 25424 KB Output is correct
17 Correct 11 ms 25144 KB Output is correct
18 Correct 9 ms 29776 KB Output is correct
19 Correct 1531 ms 159048 KB Output is correct
20 Correct 1452 ms 159304 KB Output is correct
21 Correct 1438 ms 157064 KB Output is correct
22 Correct 1426 ms 159296 KB Output is correct
23 Correct 973 ms 91464 KB Output is correct
24 Correct 94 ms 40128 KB Output is correct
25 Correct 91 ms 44360 KB Output is correct
26 Correct 78 ms 34060 KB Output is correct
27 Correct 81 ms 33868 KB Output is correct
28 Correct 83 ms 33864 KB Output is correct
29 Correct 61 ms 33916 KB Output is correct
30 Correct 68 ms 33864 KB Output is correct
31 Correct 92 ms 38140 KB Output is correct
32 Correct 36 ms 31556 KB Output is correct
33 Correct 67 ms 37016 KB Output is correct
34 Correct 215 ms 63816 KB Output is correct
35 Correct 231 ms 62024 KB Output is correct
36 Correct 196 ms 62792 KB Output is correct
37 Correct 197 ms 62932 KB Output is correct
38 Correct 194 ms 62792 KB Output is correct
39 Correct 173 ms 46556 KB Output is correct
40 Correct 146 ms 46408 KB Output is correct
41 Correct 172 ms 46152 KB Output is correct
42 Correct 154 ms 48456 KB Output is correct
43 Correct 207 ms 48712 KB Output is correct
44 Correct 190 ms 45528 KB Output is correct
45 Correct 239 ms 51016 KB Output is correct
46 Correct 200 ms 50924 KB Output is correct
47 Correct 189 ms 45640 KB Output is correct
48 Correct 212 ms 45640 KB Output is correct
49 Correct 141 ms 45440 KB Output is correct
50 Correct 138 ms 45552 KB Output is correct
51 Correct 147 ms 45392 KB Output is correct
52 Correct 164 ms 45384 KB Output is correct
53 Correct 137 ms 45388 KB Output is correct
54 Correct 161 ms 49404 KB Output is correct
55 Correct 140 ms 40948 KB Output is correct
56 Correct 158 ms 50416 KB Output is correct
57 Correct 1331 ms 190708 KB Output is correct
58 Correct 1467 ms 190316 KB Output is correct
59 Correct 1201 ms 194308 KB Output is correct
60 Correct 1331 ms 194120 KB Output is correct
61 Correct 1267 ms 194216 KB Output is correct
62 Correct 1237 ms 194284 KB Output is correct
63 Correct 691 ms 125652 KB Output is correct
64 Correct 771 ms 125560 KB Output is correct
65 Correct 1020 ms 128544 KB Output is correct
66 Correct 1041 ms 128520 KB Output is correct
67 Correct 1036 ms 128268 KB Output is correct
68 Correct 1090 ms 124560 KB Output is correct
69 Correct 1018 ms 124644 KB Output is correct
70 Correct 1061 ms 125028 KB Output is correct
71 Correct 1088 ms 124800 KB Output is correct
72 Correct 1110 ms 127304 KB Output is correct
73 Correct 689 ms 122624 KB Output is correct
74 Correct 723 ms 123000 KB Output is correct
75 Correct 701 ms 120296 KB Output is correct
76 Correct 680 ms 121816 KB Output is correct
77 Correct 683 ms 122428 KB Output is correct
78 Correct 890 ms 141308 KB Output is correct
79 Correct 684 ms 102884 KB Output is correct
80 Correct 917 ms 150484 KB Output is correct