oj.uz

Submission #336737

# Submission time Handle Problem Language Result Execution time Memory
336737 2020-12-16T15:39:38 Z amunduzbaev Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1520 ms 43260 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long 
#define ld long double 
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define prc(n) fixed << setprecision(n)
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi acos(-1);
const int inf = 1e9+7;
const int N = 1e6+5;
int n, m, aaa[N], s, a[N];

vector<int>tree;

int find(int l, int r, int lx, int rx, int x){
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return tree[x];
	int m = (lx + rx)/2;
	return max(find(l, r, lx, m, x*2), find(l, r, m+1, rx, x*2+1));
}

void update(int i, int v, int lx, int rx, int x){
	if(lx == rx){ tree[x] = v; return; }
	int m = (lx + rx)/2;
	if(i <= m) update(i, v, lx, m, x*2);
	else update(i, v, m+1, rx, x*2+1);
	tree[x] = max(tree[x*2], tree[x*2+1]);
}

void print(){
	for(int i=1;i<2*s;i++) cout<<tree[i]<<" ";
	cout<<endl;
}

void solve(){
	cin>>n>>m;
	s = 2;
	while(s < n) s<<=1;
	tree.resize(s*2, 0);
	for(int i=0;i<n;i++) cin>>a[i];
	vector<pair<pii, pii>> vv;
	for(int i=0;i<m;i++){
		int l, r, k;
		cin>>l>>r>>k;
		vv.pb({{r, l}, {k, i}});
	}
	
	sort(all(vv));
	vector<pii>ans;
	int last = 0;
	for(int i=0;i<n;i++){
		while(!ans.empty() && ans.back().ff < a[i]) ans.pop_back();
		
		bool flag = 0;
		if(ans.empty()){
			ans.pb({a[i], i+1});
			flag = 1;
		}
		
		int x = ans.back().ff, y = ans.back().ss;
		if(!flag) 	ans.pb({a[i], i+1});
		if(x > a[i])
			update(y, a[i] + x, 1, s, 1);
		
		while(last < m && vv[last].ff.ff == i+1){
			int res = find(vv[last].ff.ss, vv[last].ff.ff, 1, s, 1);
			aaa[vv[last].ss.ss] = (vv[last].ss.ff >= res);
			last++;
		}
		if(last == m) break;
	}
	//print();
	for(int i=0;i<m;i++) cout<<aaa[i]<<"\n";
	
}
 
signed main(){
	fastios
	int t = 1;
	//cin>>t;
	while(t--) solve();
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 6 ms 876 KB Output is correct
15 Correct 6 ms 876 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 748 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1492 ms 34600 KB Output is correct
2 Correct 1520 ms 39364 KB Output is correct
3 Correct 1488 ms 43260 KB Output is correct
4 Correct 1518 ms 43256 KB Output is correct
5 Correct 1297 ms 34748 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 6116 KB Output is correct
2 Correct 114 ms 6116 KB Output is correct
3 Correct 96 ms 5988 KB Output is correct
4 Correct 94 ms 6116 KB Output is correct
5 Correct 93 ms 6116 KB Output is correct
6 Correct 87 ms 5860 KB Output is correct
7 Correct 88 ms 5860 KB Output is correct
8 Correct 83 ms 6500 KB Output is correct
9 Correct 54 ms 3940 KB Output is correct
10 Correct 83 ms 6500 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 6 ms 876 KB Output is correct
15 Correct 6 ms 876 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 269 ms 12748 KB Output is correct
20 Correct 258 ms 13404 KB Output is correct
21 Correct 253 ms 13680 KB Output is correct
22 Correct 250 ms 13440 KB Output is correct
23 Correct 252 ms 13444 KB Output is correct
24 Correct 214 ms 13452 KB Output is correct
25 Correct 211 ms 13404 KB Output is correct
26 Correct 220 ms 13564 KB Output is correct
27 Correct 215 ms 13404 KB Output is correct
28 Correct 218 ms 13404 KB Output is correct
29 Correct 221 ms 13404 KB Output is correct
30 Correct 214 ms 13432 KB Output is correct
31 Correct 222 ms 13532 KB Output is correct
32 Correct 215 ms 13424 KB Output is correct
33 Correct 221 ms 13532 KB Output is correct
34 Correct 205 ms 13404 KB Output is correct
35 Correct 204 ms 13404 KB Output is correct
36 Correct 215 ms 13488 KB Output is correct
37 Correct 196 ms 13532 KB Output is correct
38 Correct 203 ms 13404 KB Output is correct
39 Correct 212 ms 12656 KB Output is correct
40 Correct 157 ms 10844 KB Output is correct
41 Correct 189 ms 13916 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 6 ms 876 KB Output is correct
15 Correct 6 ms 876 KB Output is correct
16 Correct 5 ms 748 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 748 KB Output is correct
19 Correct 1492 ms 34600 KB Output is correct
20 Correct 1520 ms 39364 KB Output is correct
21 Correct 1488 ms 43260 KB Output is correct
22 Correct 1518 ms 43256 KB Output is correct
23 Correct 1297 ms 34748 KB Output is correct
24 Correct 114 ms 6116 KB Output is correct
25 Correct 114 ms 6116 KB Output is correct
26 Correct 96 ms 5988 KB Output is correct
27 Correct 94 ms 6116 KB Output is correct
28 Correct 93 ms 6116 KB Output is correct
29 Correct 87 ms 5860 KB Output is correct
30 Correct 88 ms 5860 KB Output is correct
31 Correct 83 ms 6500 KB Output is correct
32 Correct 54 ms 3940 KB Output is correct
33 Correct 83 ms 6500 KB Output is correct
34 Correct 269 ms 12748 KB Output is correct
35 Correct 258 ms 13404 KB Output is correct
36 Correct 253 ms 13680 KB Output is correct
37 Correct 250 ms 13440 KB Output is correct
38 Correct 252 ms 13444 KB Output is correct
39 Correct 214 ms 13452 KB Output is correct
40 Correct 211 ms 13404 KB Output is correct
41 Correct 220 ms 13564 KB Output is correct
42 Correct 215 ms 13404 KB Output is correct
43 Correct 218 ms 13404 KB Output is correct
44 Correct 221 ms 13404 KB Output is correct
45 Correct 214 ms 13432 KB Output is correct
46 Correct 222 ms 13532 KB Output is correct
47 Correct 215 ms 13424 KB Output is correct
48 Correct 221 ms 13532 KB Output is correct
49 Correct 205 ms 13404 KB Output is correct
50 Correct 204 ms 13404 KB Output is correct
51 Correct 215 ms 13488 KB Output is correct
52 Correct 196 ms 13532 KB Output is correct
53 Correct 203 ms 13404 KB Output is correct
54 Correct 212 ms 12656 KB Output is correct
55 Correct 157 ms 10844 KB Output is correct
56 Correct 189 ms 13916 KB Output is correct
57 Correct 1495 ms 34836 KB Output is correct
58 Correct 1482 ms 34876 KB Output is correct
59 Correct 1457 ms 34876 KB Output is correct
60 Correct 1486 ms 34788 KB Output is correct
61 Correct 1453 ms 35004 KB Output is correct
62 Correct 1462 ms 34876 KB Output is correct
63 Correct 1116 ms 34620 KB Output is correct
64 Correct 1113 ms 34620 KB Output is correct
65 Correct 1252 ms 35004 KB Output is correct
66 Correct 1256 ms 34876 KB Output is correct
67 Correct 1260 ms 34840 KB Output is correct
68 Correct 1265 ms 34748 KB Output is correct
69 Correct 1289 ms 34748 KB Output is correct
70 Correct 1289 ms 35056 KB Output is correct
71 Correct 1284 ms 34748 KB Output is correct
72 Correct 1296 ms 34740 KB Output is correct
73 Correct 1058 ms 34620 KB Output is correct
74 Correct 1124 ms 34684 KB Output is correct
75 Correct 1090 ms 34492 KB Output is correct
76 Correct 1057 ms 34620 KB Output is correct
77 Correct 1107 ms 34620 KB Output is correct
78 Correct 1201 ms 34472 KB Output is correct
79 Correct 839 ms 28624 KB Output is correct
80 Correct 1089 ms 42428 KB Output is correct