oj.uz

Submission #334537

# Submission time Handle Problem Language Result Execution time Memory
334537 2020-12-09T10:58:51 Z Trickster Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
77 / 100
 3000 ms 262144 KB 
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>
 
#define N 1000010
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <int, int>
 
using namespace std;
 
int MX;
int n, q;
int v[N];
int arr[N];
pii T[N*4];
int l, r, x;
vector <int> E[N*4];
 
void uni(int CEP, int SAG, int node)
{
	vector <int> res;
	pii ans = {-1, -1};
	
	if(node == 0) {
		int a = lower_bound(E[SAG].begin(), E[SAG].end(), MX) - E[SAG].begin();
		a--;
		
		
		if(T[CEP].ss == -1 || T[SAG].ss == -1) { ans = (T[CEP].ss == -1 ? T[SAG] : T[CEP]); }
		else {
			if(T[CEP].ff + T[CEP].ss >= T[SAG].ff + T[SAG].ss) ans = T[CEP];
			else ans = T[SAG];
		}
		
		if(a != -1) {
			int x = E[SAG][a];
			
			if(ans.ss == -1 || ans.ff + ans.ss < MX + x) ans = {MX, x};
		}
		
		if(T[node].ss == -1 || (ans.ss != -1 && ans.ff+ans.ss >= T[node].ff + T[node].ss)) T[node] = ans;
		
		MX = max(MX, E[SAG].back());
		
		return;
	}
	
	int pos = 0, pos2 = 0;
	while(pos < E[CEP].size() && pos2 < E[SAG].size()) {
		if(E[CEP][pos] <= E[SAG][pos2]) res.pb(E[CEP][pos++]);
		
		else res.pb(E[SAG][pos2++]);
	}
	
	int a = pos2-1;
	
	while(pos < E[CEP].size()) res.pb(E[CEP][pos++]);
	while(pos2 < E[SAG].size()) res.pb(E[SAG][pos2++]);
	
	if(T[CEP].ss == -1 || T[SAG].ss == -1) { ans = (T[CEP].ss == -1 ? T[SAG] : T[CEP]); }
	else {
		if(T[CEP].ff + T[CEP].ss >= T[SAG].ff + T[SAG].ss) ans = T[CEP];
		else ans = T[SAG];
	}
	
	if(a != -1) {
		int x = E[SAG][a];
		
		if(ans.ss == -1 || ans.ff + ans.ss < E[CEP].back() + x) ans = {E[CEP].back(), x};
	}
	
	if(T[node].ss == -1 || (ans.ss != -1 && ans.ff+ans.ss >= T[node].ff + T[node].ss)) T[node] = ans;
	
	E[node].clear();
	for(auto i: res) E[node].pb(i);
}
 
void build(int l, int r, int node)
{
	if(l == r) {
		T[node] = {v[l], -1};
		E[node].pb(v[l]);
		return;
	}
	
	build(l, (l+r)/2, node*2);
	build((l+r)/2+1, r, node*2+1);
	
	uni(node*2, node*2+1, node);
} 
void tap(int a, int b, int l, int r, int node)
{
	if(l > b || r < a) return;
	
	if(l >= a && r <= b) {
		uni(0, node, 0);
		return;
	}
	
	tap(a, b, l, (l+r)/2, node*2);
	tap(a, b, (l+r)/2+1, r, node*2+1);
}
 
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> q;
	
    int mn = 1e9;
	for(int i = 1; i <= n; i++) cin >> v[i], mn = min(mn, v[i]);
	
    for(int i = 2; i <= n; i++) {
        arr[i] = arr[i-1];

        if(v[i] < v[i-1]) arr[i]++;
    }

	build(1, n, 1);
	
	for(int i = 1; i <= q; i++) {
		cin >> l >> r >> x;

        if(mn > x) {
            int now = arr[r] - arr[l];

            if(now) puts("0");
            else puts("1");

            continue;
        }

		MX = 0;
		T[0] = {-1, -1};
		tap(l, r, 1, n, 1);
		
		if(T[0].ss == -1 || T[0].ff + T[0].ss <= x) puts("1");
		else puts("0");
	}
}

Compilation message

sortbooks.cpp: In function 'void uni(int, int, int)':
sortbooks.cpp:58:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  while(pos < E[CEP].size() && pos2 < E[SAG].size()) {
      |        ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:58:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  while(pos < E[CEP].size() && pos2 < E[SAG].size()) {
      |                               ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:66:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  while(pos < E[CEP].size()) res.pb(E[CEP][pos++]);
      |        ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:67:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  while(pos2 < E[SAG].size()) res.pb(E[SAG][pos2++]);
      |        ~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 60 ms 94316 KB Output is correct
3 Correct 62 ms 94444 KB Output is correct
4 Correct 61 ms 94316 KB Output is correct
5 Correct 61 ms 94316 KB Output is correct
6 Correct 62 ms 94316 KB Output is correct
7 Correct 61 ms 94316 KB Output is correct
8 Correct 60 ms 94316 KB Output is correct
9 Correct 62 ms 94316 KB Output is correct
10 Correct 61 ms 94444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 60 ms 94316 KB Output is correct
3 Correct 62 ms 94444 KB Output is correct
4 Correct 61 ms 94316 KB Output is correct
5 Correct 61 ms 94316 KB Output is correct
6 Correct 62 ms 94316 KB Output is correct
7 Correct 61 ms 94316 KB Output is correct
8 Correct 60 ms 94316 KB Output is correct
9 Correct 62 ms 94316 KB Output is correct
10 Correct 61 ms 94444 KB Output is correct
11 Correct 63 ms 94572 KB Output is correct
12 Correct 66 ms 95084 KB Output is correct
13 Correct 67 ms 95164 KB Output is correct
14 Correct 69 ms 95084 KB Output is correct
15 Correct 69 ms 95212 KB Output is correct
16 Correct 67 ms 95212 KB Output is correct
17 Correct 67 ms 94828 KB Output is correct
18 Correct 67 ms 95212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1294 ms 258076 KB Output is correct
2 Correct 1327 ms 258324 KB Output is correct
3 Correct 1311 ms 262144 KB Output is correct
4 Correct 1345 ms 262144 KB Output is correct
5 Correct 1191 ms 262144 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 111044 KB Output is correct
2 Correct 300 ms 110916 KB Output is correct
3 Correct 344 ms 110916 KB Output is correct
4 Correct 342 ms 110916 KB Output is correct
5 Correct 340 ms 111044 KB Output is correct
6 Correct 258 ms 110916 KB Output is correct
7 Correct 262 ms 111044 KB Output is correct
8 Correct 290 ms 110916 KB Output is correct
9 Correct 102 ms 94792 KB Output is correct
10 Correct 280 ms 111044 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 60 ms 94316 KB Output is correct
3 Correct 62 ms 94444 KB Output is correct
4 Correct 61 ms 94316 KB Output is correct
5 Correct 61 ms 94316 KB Output is correct
6 Correct 62 ms 94316 KB Output is correct
7 Correct 61 ms 94316 KB Output is correct
8 Correct 60 ms 94316 KB Output is correct
9 Correct 62 ms 94316 KB Output is correct
10 Correct 61 ms 94444 KB Output is correct
11 Correct 63 ms 94572 KB Output is correct
12 Correct 66 ms 95084 KB Output is correct
13 Correct 67 ms 95164 KB Output is correct
14 Correct 69 ms 95084 KB Output is correct
15 Correct 69 ms 95212 KB Output is correct
16 Correct 67 ms 95212 KB Output is correct
17 Correct 67 ms 94828 KB Output is correct
18 Correct 67 ms 95212 KB Output is correct
19 Correct 780 ms 128592 KB Output is correct
20 Correct 780 ms 128572 KB Output is correct
21 Correct 600 ms 128444 KB Output is correct
22 Correct 595 ms 128572 KB Output is correct
23 Correct 610 ms 128572 KB Output is correct
24 Correct 529 ms 128572 KB Output is correct
25 Correct 540 ms 128572 KB Output is correct
26 Correct 710 ms 128572 KB Output is correct
27 Correct 710 ms 128572 KB Output is correct
28 Correct 734 ms 128572 KB Output is correct
29 Correct 761 ms 128552 KB Output is correct
30 Correct 751 ms 128724 KB Output is correct
31 Correct 762 ms 128820 KB Output is correct
32 Correct 753 ms 128572 KB Output is correct
33 Correct 756 ms 128696 KB Output is correct
34 Correct 520 ms 128572 KB Output is correct
35 Correct 516 ms 128576 KB Output is correct
36 Correct 514 ms 128572 KB Output is correct
37 Correct 516 ms 128572 KB Output is correct
38 Correct 522 ms 128572 KB Output is correct
39 Correct 651 ms 128572 KB Output is correct
40 Correct 421 ms 113380 KB Output is correct
41 Correct 589 ms 128572 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94316 KB Output is correct
2 Correct 60 ms 94316 KB Output is correct
3 Correct 62 ms 94444 KB Output is correct
4 Correct 61 ms 94316 KB Output is correct
5 Correct 61 ms 94316 KB Output is correct
6 Correct 62 ms 94316 KB Output is correct
7 Correct 61 ms 94316 KB Output is correct
8 Correct 60 ms 94316 KB Output is correct
9 Correct 62 ms 94316 KB Output is correct
10 Correct 61 ms 94444 KB Output is correct
11 Correct 63 ms 94572 KB Output is correct
12 Correct 66 ms 95084 KB Output is correct
13 Correct 67 ms 95164 KB Output is correct
14 Correct 69 ms 95084 KB Output is correct
15 Correct 69 ms 95212 KB Output is correct
16 Correct 67 ms 95212 KB Output is correct
17 Correct 67 ms 94828 KB Output is correct
18 Correct 67 ms 95212 KB Output is correct
19 Correct 1294 ms 258076 KB Output is correct
20 Correct 1327 ms 258324 KB Output is correct
21 Correct 1311 ms 262144 KB Output is correct
22 Correct 1345 ms 262144 KB Output is correct
23 Correct 1191 ms 262144 KB Output is correct
24 Correct 357 ms 111044 KB Output is correct
25 Correct 300 ms 110916 KB Output is correct
26 Correct 344 ms 110916 KB Output is correct
27 Correct 342 ms 110916 KB Output is correct
28 Correct 340 ms 111044 KB Output is correct
29 Correct 258 ms 110916 KB Output is correct
30 Correct 262 ms 111044 KB Output is correct
31 Correct 290 ms 110916 KB Output is correct
32 Correct 102 ms 94792 KB Output is correct
33 Correct 280 ms 111044 KB Output is correct
34 Correct 780 ms 128592 KB Output is correct
35 Correct 780 ms 128572 KB Output is correct
36 Correct 600 ms 128444 KB Output is correct
37 Correct 595 ms 128572 KB Output is correct
38 Correct 610 ms 128572 KB Output is correct
39 Correct 529 ms 128572 KB Output is correct
40 Correct 540 ms 128572 KB Output is correct
41 Correct 710 ms 128572 KB Output is correct
42 Correct 710 ms 128572 KB Output is correct
43 Correct 734 ms 128572 KB Output is correct
44 Correct 761 ms 128552 KB Output is correct
45 Correct 751 ms 128724 KB Output is correct
46 Correct 762 ms 128820 KB Output is correct
47 Correct 753 ms 128572 KB Output is correct
48 Correct 756 ms 128696 KB Output is correct
49 Correct 520 ms 128572 KB Output is correct
50 Correct 516 ms 128576 KB Output is correct
51 Correct 514 ms 128572 KB Output is correct
52 Correct 516 ms 128572 KB Output is correct
53 Correct 522 ms 128572 KB Output is correct
54 Correct 651 ms 128572 KB Output is correct
55 Correct 421 ms 113380 KB Output is correct
56 Correct 589 ms 128572 KB Output is correct
57 Execution timed out 3091 ms 261952 KB Time limit exceeded
58 Halted 0 ms 0 KB -