oj.uz

Submission #545692

# Submission time Handle Problem Language Result Execution time Memory
545692 2022-04-05T07:54:55 Z BackNoob Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1067 ms 181224 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1) 
#define TASK "task"
#define sz(s) (int) (s).size()

using namespace std;
const int mxN = 2e6 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct item{
	int r , c , idx;
};

int n;
int q;
int a[mxN];
int lef[mxN];
int bit[mxN];
vector<item> query[mxN];
vector<int> val[mxN];
bool ans[mxN];

void update(int pos , int val)
{
	for(; pos <= n ; pos += pos & (-pos)) maximize(bit[pos] , val);
}
int getmax(int pos)
{
	int res = 0;
	for(; pos > 0 ; pos -= pos & -pos) maximize(res , bit[pos]);
	return res;
}


void solve()
{
	cin >> n >> q;
	for(int i = 1 ; i <= n ; i++) cin >> a[i];

	stack<int> s;
	for(int i = 1 ; i <= n ; i++) {
		while(sz(s) && a[s.top()] <= a[i]) s.pop();
		if(sz(s)) lef[i] = s.top();
		else lef[i] = 0;
		s.push(i);
	} 

	// for(int i = 1 ; i <= n ; i++) cout << lef[i] << ' ';
	// cout << endl;


	for(int i = 1 ; i <= q ; i++) {
		int l, r, c;
		cin >> l >> r >> c;
		query[l].pb({r , c , i});
	}

	for(int i = 1 ; i <= n ; i++) val[lef[i]].pb(i);
	for(int i = n ; i >= 1 ; i--) {
		for(auto it : val[i]) {
			update(it , a[i] + a[it]);
		}

		for(auto it : query[i]) {
			// cout << it.idx << endl;
			ans[it.idx] = (getmax(it.r) <= it.c);
		}
	}

	for(int i = 1 ; i <= q ; i++) cout << ans[i] << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(TASK".in" , "r" , stdin);
    //freopen(TASK".out" , "w" , stdout);
    
    int tc = 1;
    //cin >> tc;
    while(tc--) {
    	solve();
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94156 KB Output is correct
2 Correct 55 ms 94272 KB Output is correct
3 Correct 49 ms 94272 KB Output is correct
4 Correct 46 ms 94260 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 44 ms 94332 KB Output is correct
7 Correct 45 ms 94328 KB Output is correct
8 Correct 46 ms 94232 KB Output is correct
9 Correct 47 ms 94224 KB Output is correct
10 Correct 45 ms 94220 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94156 KB Output is correct
2 Correct 55 ms 94272 KB Output is correct
3 Correct 49 ms 94272 KB Output is correct
4 Correct 46 ms 94260 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 44 ms 94332 KB Output is correct
7 Correct 45 ms 94328 KB Output is correct
8 Correct 46 ms 94232 KB Output is correct
9 Correct 47 ms 94224 KB Output is correct
10 Correct 45 ms 94220 KB Output is correct
11 Correct 46 ms 94460 KB Output is correct
12 Correct 46 ms 94584 KB Output is correct
13 Correct 50 ms 94504 KB Output is correct
14 Correct 55 ms 94696 KB Output is correct
15 Correct 49 ms 94616 KB Output is correct
16 Correct 53 ms 94480 KB Output is correct
17 Correct 55 ms 94564 KB Output is correct
18 Correct 48 ms 94560 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 959 ms 178756 KB Output is correct
2 Correct 1048 ms 179852 KB Output is correct
3 Correct 1020 ms 179740 KB Output is correct
4 Correct 947 ms 179788 KB Output is correct
5 Correct 877 ms 163792 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 101564 KB Output is correct
2 Correct 111 ms 101064 KB Output is correct
3 Correct 101 ms 99932 KB Output is correct
4 Correct 101 ms 100000 KB Output is correct
5 Correct 103 ms 100168 KB Output is correct
6 Correct 99 ms 99400 KB Output is correct
7 Correct 88 ms 99368 KB Output is correct
8 Correct 91 ms 99684 KB Output is correct
9 Correct 82 ms 97376 KB Output is correct
10 Correct 97 ms 99664 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94156 KB Output is correct
2 Correct 55 ms 94272 KB Output is correct
3 Correct 49 ms 94272 KB Output is correct
4 Correct 46 ms 94260 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 44 ms 94332 KB Output is correct
7 Correct 45 ms 94328 KB Output is correct
8 Correct 46 ms 94232 KB Output is correct
9 Correct 47 ms 94224 KB Output is correct
10 Correct 45 ms 94220 KB Output is correct
11 Correct 46 ms 94460 KB Output is correct
12 Correct 46 ms 94584 KB Output is correct
13 Correct 50 ms 94504 KB Output is correct
14 Correct 55 ms 94696 KB Output is correct
15 Correct 49 ms 94616 KB Output is correct
16 Correct 53 ms 94480 KB Output is correct
17 Correct 55 ms 94564 KB Output is correct
18 Correct 48 ms 94560 KB Output is correct
19 Correct 207 ms 111484 KB Output is correct
20 Correct 209 ms 111516 KB Output is correct
21 Correct 176 ms 110440 KB Output is correct
22 Correct 190 ms 110440 KB Output is correct
23 Correct 183 ms 110368 KB Output is correct
24 Correct 151 ms 107668 KB Output is correct
25 Correct 161 ms 107884 KB Output is correct
26 Correct 183 ms 107992 KB Output is correct
27 Correct 170 ms 108020 KB Output is correct
28 Correct 189 ms 107924 KB Output is correct
29 Correct 180 ms 108348 KB Output is correct
30 Correct 183 ms 108364 KB Output is correct
31 Correct 190 ms 108340 KB Output is correct
32 Correct 187 ms 108352 KB Output is correct
33 Correct 176 ms 108436 KB Output is correct
34 Correct 157 ms 106884 KB Output is correct
35 Correct 147 ms 106900 KB Output is correct
36 Correct 144 ms 106680 KB Output is correct
37 Correct 151 ms 106656 KB Output is correct
38 Correct 146 ms 106880 KB Output is correct
39 Correct 168 ms 107204 KB Output is correct
40 Correct 151 ms 104704 KB Output is correct
41 Correct 157 ms 106420 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94156 KB Output is correct
2 Correct 55 ms 94272 KB Output is correct
3 Correct 49 ms 94272 KB Output is correct
4 Correct 46 ms 94260 KB Output is correct
5 Correct 45 ms 94284 KB Output is correct
6 Correct 44 ms 94332 KB Output is correct
7 Correct 45 ms 94328 KB Output is correct
8 Correct 46 ms 94232 KB Output is correct
9 Correct 47 ms 94224 KB Output is correct
10 Correct 45 ms 94220 KB Output is correct
11 Correct 46 ms 94460 KB Output is correct
12 Correct 46 ms 94584 KB Output is correct
13 Correct 50 ms 94504 KB Output is correct
14 Correct 55 ms 94696 KB Output is correct
15 Correct 49 ms 94616 KB Output is correct
16 Correct 53 ms 94480 KB Output is correct
17 Correct 55 ms 94564 KB Output is correct
18 Correct 48 ms 94560 KB Output is correct
19 Correct 959 ms 178756 KB Output is correct
20 Correct 1048 ms 179852 KB Output is correct
21 Correct 1020 ms 179740 KB Output is correct
22 Correct 947 ms 179788 KB Output is correct
23 Correct 877 ms 163792 KB Output is correct
24 Correct 109 ms 101564 KB Output is correct
25 Correct 111 ms 101064 KB Output is correct
26 Correct 101 ms 99932 KB Output is correct
27 Correct 101 ms 100000 KB Output is correct
28 Correct 103 ms 100168 KB Output is correct
29 Correct 99 ms 99400 KB Output is correct
30 Correct 88 ms 99368 KB Output is correct
31 Correct 91 ms 99684 KB Output is correct
32 Correct 82 ms 97376 KB Output is correct
33 Correct 97 ms 99664 KB Output is correct
34 Correct 207 ms 111484 KB Output is correct
35 Correct 209 ms 111516 KB Output is correct
36 Correct 176 ms 110440 KB Output is correct
37 Correct 190 ms 110440 KB Output is correct
38 Correct 183 ms 110368 KB Output is correct
39 Correct 151 ms 107668 KB Output is correct
40 Correct 161 ms 107884 KB Output is correct
41 Correct 183 ms 107992 KB Output is correct
42 Correct 170 ms 108020 KB Output is correct
43 Correct 189 ms 107924 KB Output is correct
44 Correct 180 ms 108348 KB Output is correct
45 Correct 183 ms 108364 KB Output is correct
46 Correct 190 ms 108340 KB Output is correct
47 Correct 187 ms 108352 KB Output is correct
48 Correct 176 ms 108436 KB Output is correct
49 Correct 157 ms 106884 KB Output is correct
50 Correct 147 ms 106900 KB Output is correct
51 Correct 144 ms 106680 KB Output is correct
52 Correct 151 ms 106656 KB Output is correct
53 Correct 146 ms 106880 KB Output is correct
54 Correct 168 ms 107204 KB Output is correct
55 Correct 151 ms 104704 KB Output is correct
56 Correct 157 ms 106420 KB Output is correct
57 Correct 1045 ms 181200 KB Output is correct
58 Correct 1067 ms 181224 KB Output is correct
59 Correct 963 ms 178768 KB Output is correct
60 Correct 996 ms 178552 KB Output is correct
61 Correct 965 ms 178480 KB Output is correct
62 Correct 953 ms 178568 KB Output is correct
63 Correct 635 ms 157352 KB Output is correct
64 Correct 649 ms 157152 KB Output is correct
65 Correct 859 ms 162708 KB Output is correct
66 Correct 834 ms 162700 KB Output is correct
67 Correct 892 ms 162876 KB Output is correct
68 Correct 895 ms 164848 KB Output is correct
69 Correct 875 ms 165040 KB Output is correct
70 Correct 894 ms 164904 KB Output is correct
71 Correct 873 ms 164416 KB Output is correct
72 Correct 913 ms 164452 KB Output is correct
73 Correct 552 ms 154828 KB Output is correct
74 Correct 611 ms 155664 KB Output is correct
75 Correct 577 ms 154948 KB Output is correct
76 Correct 580 ms 154680 KB Output is correct
77 Correct 565 ms 154708 KB Output is correct
78 Correct 781 ms 160252 KB Output is correct
79 Correct 595 ms 144484 KB Output is correct
80 Correct 734 ms 156000 KB Output is correct