oj.uz

Submission #523743

# Submission time Handle Problem Language Result Execution time Memory
523743 2022-02-08T05:58:17 Z Kalashnikov Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 1913 ms 262148 KB 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 1e6+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int a[N];
struct DO{
	int mn = -1, mx , inv;
	set<int> v;
}t[4*N] , null;
int n, m;

void merge(DO &u , DO L , DO R) {
	if(L.mn == -1) u = R;
	else if(R.mn == -1) u = L;
	else {
		u.mn = min(L.mn , R.mn);
		u.mx = max(L.mx , R.mx);
		u.inv = max(L.inv , R.inv);
		auto it = R.v.lower_bound(L.mx);
		if(it != R.v.begin()) {
			--it;
			u.inv = max(u.inv , L.mx + *it);
		}
		if(L.v.size() < R.v.size()) {
			swap(L , R);
		}
		swap(u.v , L.v);
		for(auto x: R.v) {
			u.v.insert(x);
		}
	}
}

void build(int u = 1, int ul = 1 , int ur = n) {
	if(ul == ur) {
		t[u].mn = t[u].mx = a[ul];
		t[u].inv = 0;
		t[u].v.insert(a[ul]);
		return;
	}
	
	int um= ul+ur >> 1;
	build(u<<1 , ul , um);
	build(u<<1|1 , um+1 , ur);
	merge(t[u] , t[u<<1] , t[u<<1|1]);
}

DO get(int l , int r , int u = 1, int ul = 1, int ur = n) {
	if(l <= ul && ur <= r) {
		return t[u];
	}
	if(r < ul || ur < l) {
		return null;
	}
	
	int um = ul+ur >> 1;
	DO res;
	merge(res , get(l , r , u<<1 , ul , um) , get(l , r , u<<1|1 , um+1 , ur));
	return res;
}

void solve(int tc) {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	build();
	while(m --) {
		int l , r , x;
		cin >> l >> r >> x;
		cout << (get(l , r).inv <= x) << '\n';
	}
}
/*
*/
main() {
    ios;
    int tt = 1 , tc = 0;
    // cin >> tt;
    while(tt --) {
        solve(++tc);
    }
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int um= ul+ur >> 1;
      |          ~~^~~
sortbooks.cpp: In function 'DO get(int, int, int, int, int)':
sortbooks.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int um = ul+ur >> 1;
      |           ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:86:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   86 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 250684 KB Output is correct
2 Correct 102 ms 250708 KB Output is correct
3 Correct 107 ms 250788 KB Output is correct
4 Correct 113 ms 250752 KB Output is correct
5 Correct 111 ms 250916 KB Output is correct
6 Correct 119 ms 251040 KB Output is correct
7 Correct 116 ms 251036 KB Output is correct
8 Correct 125 ms 251068 KB Output is correct
9 Correct 109 ms 250948 KB Output is correct
10 Correct 106 ms 250856 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 250684 KB Output is correct
2 Correct 102 ms 250708 KB Output is correct
3 Correct 107 ms 250788 KB Output is correct
4 Correct 113 ms 250752 KB Output is correct
5 Correct 111 ms 250916 KB Output is correct
6 Correct 119 ms 251040 KB Output is correct
7 Correct 116 ms 251036 KB Output is correct
8 Correct 125 ms 251068 KB Output is correct
9 Correct 109 ms 250948 KB Output is correct
10 Correct 106 ms 250856 KB Output is correct
11 Correct 342 ms 251832 KB Output is correct
12 Correct 846 ms 254276 KB Output is correct
13 Correct 1012 ms 254296 KB Output is correct
14 Correct 1629 ms 254440 KB Output is correct
15 Correct 1570 ms 254532 KB Output is correct
16 Correct 1913 ms 254412 KB Output is correct
17 Correct 879 ms 253692 KB Output is correct
18 Correct 115 ms 251372 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 250684 KB Output is correct
2 Correct 102 ms 250708 KB Output is correct
3 Correct 107 ms 250788 KB Output is correct
4 Correct 113 ms 250752 KB Output is correct
5 Correct 111 ms 250916 KB Output is correct
6 Correct 119 ms 251040 KB Output is correct
7 Correct 116 ms 251036 KB Output is correct
8 Correct 125 ms 251068 KB Output is correct
9 Correct 109 ms 250948 KB Output is correct
10 Correct 106 ms 250856 KB Output is correct
11 Correct 342 ms 251832 KB Output is correct
12 Correct 846 ms 254276 KB Output is correct
13 Correct 1012 ms 254296 KB Output is correct
14 Correct 1629 ms 254440 KB Output is correct
15 Correct 1570 ms 254532 KB Output is correct
16 Correct 1913 ms 254412 KB Output is correct
17 Correct 879 ms 253692 KB Output is correct
18 Correct 115 ms 251372 KB Output is correct
19 Runtime error 143 ms 262148 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 106 ms 250684 KB Output is correct
2 Correct 102 ms 250708 KB Output is correct
3 Correct 107 ms 250788 KB Output is correct
4 Correct 113 ms 250752 KB Output is correct
5 Correct 111 ms 250916 KB Output is correct
6 Correct 119 ms 251040 KB Output is correct
7 Correct 116 ms 251036 KB Output is correct
8 Correct 125 ms 251068 KB Output is correct
9 Correct 109 ms 250948 KB Output is correct
10 Correct 106 ms 250856 KB Output is correct
11 Correct 342 ms 251832 KB Output is correct
12 Correct 846 ms 254276 KB Output is correct
13 Correct 1012 ms 254296 KB Output is correct
14 Correct 1629 ms 254440 KB Output is correct
15 Correct 1570 ms 254532 KB Output is correct
16 Correct 1913 ms 254412 KB Output is correct
17 Correct 879 ms 253692 KB Output is correct
18 Correct 115 ms 251372 KB Output is correct
19 Runtime error 205 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -