oj.uz

Submission #1040329

# Submission time Handle Problem Language Result Execution time Memory
1040329 2024-08-01T01:14:45 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
34 / 100
 377 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
int N=1<<19;
vector<int> bin(2*N, 0);
vector<set<int>> T(2*N);
int ans=0;
int query(int id, int l, int r, int a, int b, int mx)
{
    if(l>=b||r<=a) 
		return -1e9;
    if(a<=l&&r<=b)
    {
        ans=max(ans, bin[id]);
        if(T[id].lower_bound(mx)!=T[id].begin())
        {
            int en=*(--T[id].lower_bound(mx));
            ans=max(ans, mx+en);
        }
        return *(--T[id].end());
    }
    int mid=(l+r)/2;
    mx=max(mx, query(id*2, l, mid, a, b, mx));
    mx=max(mx, query(id*2+1, mid, r, a, b, mx));
    return mx;
}
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i=0; i<n; i++)
    {
        int a;
        cin >> a;
        T[i+N].insert(a);
    }
    for(int i=n; i<N; i++) 
		T[i+N].insert(1e9);
    for(int i=N-1; i>0; i--)
    {
        for (int x:T[i*2]) 
			T[i].insert(x);
        for (int x:T[i*2+1]) 
			T[i].insert(x);
        bin[i]=max(bin[i*2], bin[i*2+1]);
        int mx=*(--T[i*2].end());
        if (T[i*2+1].lower_bound(mx)!=T[i*2+1].begin())
            bin[i]=max(bin[i], mx+*(--T[i*2+1].lower_bound(mx)));
    } 
    while(q--)
    {
        int l, r, mood;
        cin >> l >> r >> mood;
        l--;
        ans=0;
        query(1, 0, N, l, r, -1e9);
        if(ans<=mood) 
			cout << "1\n";
        else
			cout << "0\n";
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 102860 KB Output is correct
2 Correct 61 ms 103008 KB Output is correct
3 Correct 63 ms 102992 KB Output is correct
4 Correct 60 ms 102992 KB Output is correct
5 Correct 61 ms 103216 KB Output is correct
6 Correct 62 ms 103420 KB Output is correct
7 Correct 63 ms 103256 KB Output is correct
8 Correct 62 ms 103256 KB Output is correct
9 Correct 61 ms 103032 KB Output is correct
10 Correct 65 ms 103000 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 102860 KB Output is correct
2 Correct 61 ms 103008 KB Output is correct
3 Correct 63 ms 102992 KB Output is correct
4 Correct 60 ms 102992 KB Output is correct
5 Correct 61 ms 103216 KB Output is correct
6 Correct 62 ms 103420 KB Output is correct
7 Correct 63 ms 103256 KB Output is correct
8 Correct 62 ms 103256 KB Output is correct
9 Correct 61 ms 103032 KB Output is correct
10 Correct 65 ms 103000 KB Output is correct
11 Correct 67 ms 104268 KB Output is correct
12 Correct 74 ms 107092 KB Output is correct
13 Correct 72 ms 107172 KB Output is correct
14 Correct 73 ms 107344 KB Output is correct
15 Correct 72 ms 107348 KB Output is correct
16 Correct 78 ms 107372 KB Output is correct
17 Correct 79 ms 106592 KB Output is correct
18 Correct 63 ms 103156 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 162908 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 147392 KB Output is correct
2 Correct 304 ms 148052 KB Output is correct
3 Correct 148 ms 106268 KB Output is correct
4 Correct 138 ms 106044 KB Output is correct
5 Correct 136 ms 105848 KB Output is correct
6 Correct 112 ms 105808 KB Output is correct
7 Correct 116 ms 106068 KB Output is correct
8 Correct 119 ms 104876 KB Output is correct
9 Correct 87 ms 104784 KB Output is correct
10 Correct 117 ms 104804 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 102860 KB Output is correct
2 Correct 61 ms 103008 KB Output is correct
3 Correct 63 ms 102992 KB Output is correct
4 Correct 60 ms 102992 KB Output is correct
5 Correct 61 ms 103216 KB Output is correct
6 Correct 62 ms 103420 KB Output is correct
7 Correct 63 ms 103256 KB Output is correct
8 Correct 62 ms 103256 KB Output is correct
9 Correct 61 ms 103032 KB Output is correct
10 Correct 65 ms 103000 KB Output is correct
11 Correct 67 ms 104268 KB Output is correct
12 Correct 74 ms 107092 KB Output is correct
13 Correct 72 ms 107172 KB Output is correct
14 Correct 73 ms 107344 KB Output is correct
15 Correct 72 ms 107348 KB Output is correct
16 Correct 78 ms 107372 KB Output is correct
17 Correct 79 ms 106592 KB Output is correct
18 Correct 63 ms 103156 KB Output is correct
19 Runtime error 319 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 102860 KB Output is correct
2 Correct 61 ms 103008 KB Output is correct
3 Correct 63 ms 102992 KB Output is correct
4 Correct 60 ms 102992 KB Output is correct
5 Correct 61 ms 103216 KB Output is correct
6 Correct 62 ms 103420 KB Output is correct
7 Correct 63 ms 103256 KB Output is correct
8 Correct 62 ms 103256 KB Output is correct
9 Correct 61 ms 103032 KB Output is correct
10 Correct 65 ms 103000 KB Output is correct
11 Correct 67 ms 104268 KB Output is correct
12 Correct 74 ms 107092 KB Output is correct
13 Correct 72 ms 107172 KB Output is correct
14 Correct 73 ms 107344 KB Output is correct
15 Correct 72 ms 107348 KB Output is correct
16 Correct 78 ms 107372 KB Output is correct
17 Correct 79 ms 106592 KB Output is correct
18 Correct 63 ms 103156 KB Output is correct
19 Runtime error 112 ms 162908 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -