oj.uz

Submission #1108172

# Submission time Handle Problem Language Result Execution time Memory
1108172 2024-11-03T07:48:14 Z kuka_123 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1132 ms 107528 KB 
															/*Bismillahir Rahmanir Raheem*/
#include <bits/stdc++.h>
  
using namespace std;
 
#define kuka ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define FOR(n) for(int i = 0; i < n; i++)
#define ff(x, y) for( int y = 0; y < x; y++)
#define fff(x, y) for( int y = x; y <= 0; y--)
#define F first
#define S second
//#define int long long  
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll INF = LLONG_MAX;
const int inf = INT_MAX;
const double PI = acos(-1);
const int N = 1e6 + 5;
const int MOD = 1e9 ;	 
 
vector<pair<int, pair<int, int> > > g[N];
int a[N], last[N], b[N], c[N], ans[N], t[N * 4];
 
void update(int v, int l, int r, int x, int y){
	if(l == r){
		t[v] = y;
		return;
	}
	int mid = (l + r) / 2;
	if(mid >= x)update(v * 2, l, mid, x, y);
	else update(v * 2 + 1, mid + 1, r, x, y);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int get(int v, int l , int r, int L , int R){
	if(l > R or L > r) return 0;
	if(l >= L and R >= r)return t[v];
	int mid = (l + r) / 2;
	return max(get(v * 2, l , mid, L, R), get(v * 2 + 1, mid + 1, r, L, R));
}
 
void oyan(){
	int n ,q;
	cin>>n>>q;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		b[i] = a[i];
	}
	sort(b + 1, b + 1 + n);
//	for(int i = 1; i <= n; i++){
//		c[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b ;
//	}
	for(int i = 1; i <= q; i++){
		int l, r, x;
		cin>>l>>r>>x;
		g[r].pb({l, {x, i}});
	}
	stack<int> s;
	s.push(1);
	for(int i = 2; i <= n; i++){
		while(!s.empty() and a[s.top()] <= a[i])s.pop();
		if(s.empty()) last[i] = 0;
		else last[i] = s.top();
		s.push(i);
	}
	for(int i = 1; i <= n; i++){
		if(last[i])update(1, 1, n, last[i], a[last[i]] + a[i]);
		for(auto x : g[i]){
			if(get(1, 1, n, x.F, i) <= x.S.F)ans[x.S.S] = 1;
		}
	}
	for(int i = 1; i <= q; i++){
		cout<<ans[i]<<"\n";
	}
//	cout<<"\n";

	
}
 
main(){
    kuka;
	//freopen("test.txt", "r", stdin);
	//freopen("distance.in", "r", stdin);
    //freopen("distance.out", "w", stdout);
    int oylan = 1;
   	//cin>>oylan;
    while(oylan--){
        oyan();
    }
}
/*
NOTES
a/b module == (a*b^(module - 2)) % (module);
*/

Compilation message

sortbooks.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main(){
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32080 KB Output is correct
2 Correct 7 ms 30032 KB Output is correct
3 Correct 6 ms 32504 KB Output is correct
4 Correct 6 ms 32336 KB Output is correct
5 Correct 7 ms 32336 KB Output is correct
6 Correct 6 ms 32204 KB Output is correct
7 Correct 7 ms 32204 KB Output is correct
8 Correct 6 ms 32336 KB Output is correct
9 Correct 7 ms 32344 KB Output is correct
10 Correct 7 ms 32336 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32080 KB Output is correct
2 Correct 7 ms 30032 KB Output is correct
3 Correct 6 ms 32504 KB Output is correct
4 Correct 6 ms 32336 KB Output is correct
5 Correct 7 ms 32336 KB Output is correct
6 Correct 6 ms 32204 KB Output is correct
7 Correct 7 ms 32204 KB Output is correct
8 Correct 6 ms 32336 KB Output is correct
9 Correct 7 ms 32344 KB Output is correct
10 Correct 7 ms 32336 KB Output is correct
11 Correct 8 ms 32372 KB Output is correct
12 Correct 9 ms 32336 KB Output is correct
13 Correct 10 ms 32348 KB Output is correct
14 Correct 11 ms 32592 KB Output is correct
15 Correct 12 ms 32604 KB Output is correct
16 Correct 9 ms 32504 KB Output is correct
17 Correct 8 ms 32336 KB Output is correct
18 Correct 8 ms 32548 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 104264 KB Output is correct
2 Correct 1008 ms 105252 KB Output is correct
3 Correct 991 ms 105036 KB Output is correct
4 Correct 1053 ms 105484 KB Output is correct
5 Correct 950 ms 98984 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 38728 KB Output is correct
2 Correct 78 ms 38488 KB Output is correct
3 Correct 79 ms 36428 KB Output is correct
4 Correct 66 ms 36416 KB Output is correct
5 Correct 67 ms 36416 KB Output is correct
6 Correct 52 ms 36052 KB Output is correct
7 Correct 53 ms 35912 KB Output is correct
8 Correct 59 ms 36096 KB Output is correct
9 Correct 34 ms 35072 KB Output is correct
10 Correct 61 ms 36108 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32080 KB Output is correct
2 Correct 7 ms 30032 KB Output is correct
3 Correct 6 ms 32504 KB Output is correct
4 Correct 6 ms 32336 KB Output is correct
5 Correct 7 ms 32336 KB Output is correct
6 Correct 6 ms 32204 KB Output is correct
7 Correct 7 ms 32204 KB Output is correct
8 Correct 6 ms 32336 KB Output is correct
9 Correct 7 ms 32344 KB Output is correct
10 Correct 7 ms 32336 KB Output is correct
11 Correct 8 ms 32372 KB Output is correct
12 Correct 9 ms 32336 KB Output is correct
13 Correct 10 ms 32348 KB Output is correct
14 Correct 11 ms 32592 KB Output is correct
15 Correct 12 ms 32604 KB Output is correct
16 Correct 9 ms 32504 KB Output is correct
17 Correct 8 ms 32336 KB Output is correct
18 Correct 8 ms 32548 KB Output is correct
19 Correct 172 ms 45744 KB Output is correct
20 Correct 180 ms 45640 KB Output is correct
21 Correct 173 ms 44872 KB Output is correct
22 Correct 158 ms 44968 KB Output is correct
23 Correct 148 ms 44872 KB Output is correct
24 Correct 133 ms 42656 KB Output is correct
25 Correct 122 ms 42576 KB Output is correct
26 Correct 135 ms 43004 KB Output is correct
27 Correct 136 ms 42920 KB Output is correct
28 Correct 142 ms 43080 KB Output is correct
29 Correct 143 ms 43344 KB Output is correct
30 Correct 163 ms 43556 KB Output is correct
31 Correct 141 ms 43428 KB Output is correct
32 Correct 150 ms 43276 KB Output is correct
33 Correct 141 ms 43336 KB Output is correct
34 Correct 109 ms 44360 KB Output is correct
35 Correct 105 ms 44336 KB Output is correct
36 Correct 114 ms 44036 KB Output is correct
37 Correct 107 ms 44104 KB Output is correct
38 Correct 104 ms 44332 KB Output is correct
39 Correct 118 ms 42248 KB Output is correct
40 Correct 93 ms 40700 KB Output is correct
41 Correct 110 ms 41220 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 32080 KB Output is correct
2 Correct 7 ms 30032 KB Output is correct
3 Correct 6 ms 32504 KB Output is correct
4 Correct 6 ms 32336 KB Output is correct
5 Correct 7 ms 32336 KB Output is correct
6 Correct 6 ms 32204 KB Output is correct
7 Correct 7 ms 32204 KB Output is correct
8 Correct 6 ms 32336 KB Output is correct
9 Correct 7 ms 32344 KB Output is correct
10 Correct 7 ms 32336 KB Output is correct
11 Correct 8 ms 32372 KB Output is correct
12 Correct 9 ms 32336 KB Output is correct
13 Correct 10 ms 32348 KB Output is correct
14 Correct 11 ms 32592 KB Output is correct
15 Correct 12 ms 32604 KB Output is correct
16 Correct 9 ms 32504 KB Output is correct
17 Correct 8 ms 32336 KB Output is correct
18 Correct 8 ms 32548 KB Output is correct
19 Correct 1132 ms 104264 KB Output is correct
20 Correct 1008 ms 105252 KB Output is correct
21 Correct 991 ms 105036 KB Output is correct
22 Correct 1053 ms 105484 KB Output is correct
23 Correct 950 ms 98984 KB Output is correct
24 Correct 71 ms 38728 KB Output is correct
25 Correct 78 ms 38488 KB Output is correct
26 Correct 79 ms 36428 KB Output is correct
27 Correct 66 ms 36416 KB Output is correct
28 Correct 67 ms 36416 KB Output is correct
29 Correct 52 ms 36052 KB Output is correct
30 Correct 53 ms 35912 KB Output is correct
31 Correct 59 ms 36096 KB Output is correct
32 Correct 34 ms 35072 KB Output is correct
33 Correct 61 ms 36108 KB Output is correct
34 Correct 172 ms 45744 KB Output is correct
35 Correct 180 ms 45640 KB Output is correct
36 Correct 173 ms 44872 KB Output is correct
37 Correct 158 ms 44968 KB Output is correct
38 Correct 148 ms 44872 KB Output is correct
39 Correct 133 ms 42656 KB Output is correct
40 Correct 122 ms 42576 KB Output is correct
41 Correct 135 ms 43004 KB Output is correct
42 Correct 136 ms 42920 KB Output is correct
43 Correct 142 ms 43080 KB Output is correct
44 Correct 143 ms 43344 KB Output is correct
45 Correct 163 ms 43556 KB Output is correct
46 Correct 141 ms 43428 KB Output is correct
47 Correct 150 ms 43276 KB Output is correct
48 Correct 141 ms 43336 KB Output is correct
49 Correct 109 ms 44360 KB Output is correct
50 Correct 105 ms 44336 KB Output is correct
51 Correct 114 ms 44036 KB Output is correct
52 Correct 107 ms 44104 KB Output is correct
53 Correct 104 ms 44332 KB Output is correct
54 Correct 118 ms 42248 KB Output is correct
55 Correct 93 ms 40700 KB Output is correct
56 Correct 110 ms 41220 KB Output is correct
57 Correct 971 ms 107336 KB Output is correct
58 Correct 1073 ms 107528 KB Output is correct
59 Correct 1093 ms 106144 KB Output is correct
60 Correct 1027 ms 105776 KB Output is correct
61 Correct 995 ms 105908 KB Output is correct
62 Correct 1049 ms 105948 KB Output is correct
63 Correct 554 ms 94536 KB Output is correct
64 Correct 583 ms 94536 KB Output is correct
65 Correct 761 ms 97608 KB Output is correct
66 Correct 773 ms 97608 KB Output is correct
67 Correct 858 ms 97668 KB Output is correct
68 Correct 879 ms 99144 KB Output is correct
69 Correct 857 ms 99120 KB Output is correct
70 Correct 869 ms 98860 KB Output is correct
71 Correct 870 ms 98812 KB Output is correct
72 Correct 838 ms 98812 KB Output is correct
73 Correct 656 ms 94140 KB Output is correct
74 Correct 559 ms 95304 KB Output is correct
75 Correct 556 ms 94536 KB Output is correct
76 Correct 532 ms 94792 KB Output is correct
77 Correct 528 ms 94156 KB Output is correct
78 Correct 689 ms 95492 KB Output is correct
79 Correct 549 ms 84460 KB Output is correct
80 Correct 820 ms 88812 KB Output is correct