oj.uz

Submission #408847

# Submission time Handle Problem Language Result Execution time Memory
408847 2021-05-19T17:59:16 Z MohamedAhmed04 New Home (APIO18_new_home) C++14
100 / 100
 4502 ms 178784 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 3e5 + 10 ;

int ans[MAX] ;
int n , k , q ;

multiset<int>s[MAX] ;

vector<int>v ;
vector< array<int , 4> >queries ;

int tree[4 * MAX] ;
multiset<int>vals[4 * MAX] ;

void update(int node , int l , int r , int idx , int val)
{
	if(idx > r || idx < l)
		return ;
	if(l == r)
	{
		if(val < 0)
			vals[node].erase(vals[node].find(-1 * val)) ;
		else
			vals[node].insert(val) ;
		if(vals[node].size())
			tree[node] = *vals[node].rbegin() ;
		else
			tree[node] = 0 ;
		return ;
	}
	int mid = (l + r) >> 1 ;
	update(node << 1 , l , mid , idx , val) ;
	update(node << 1 | 1 , mid+1 , r , idx , val) ;
	tree[node] = max(tree[node << 1]  , tree[node << 1 | 1]) ;
}

int query(int node , int l , int r , int from , int to)
{
	if(from > r || to < l)
		return 0 ;
	if(l >= from && r <= to)
		return tree[node] ;
	int mid = (l + r) >> 1 ;
	int x = query(node << 1 , l , mid , from , to) ;
	int y = query(node << 1 | 1 , mid+1 , r , from , to) ;
	return max(x , y) ;
}

bool cmp(array<int , 4>&a , array<int , 4>&b)
{
	if(a[0] != b[0])
		return a[0] < b[0] ;
	else
		return a[3] < b[3] ;
}

int getidx(int x)
{
	return lower_bound(v.begin() , v.end() , x) - v.begin() ;
}

void Add(int x , int t)
{
	int prv = *prev(s[t].lower_bound(x)) ;
	int nxt = *s[t].lower_bound(x) ;
	update(1 , 0 , n , getidx(prv) , -1 * nxt) ;
	update(1 , 0 , n , getidx(prv) , x) ;
	update(1 , 0 , n , getidx(x) , nxt) ;
	s[t].insert(x) ;
}

void Erase(int x , int t)
{
	s[t].erase(s[t].find(x)) ;
	int prv = *prev(s[t].lower_bound(x)) ;
	int nxt = *s[t].lower_bound(x) ;
	update(1 , 0 , n , getidx(prv) , -1 * x) ;
	update(1 , 0 , n , getidx(prv) , nxt) ;
	update(1 , 0 , n , getidx(x) , -1 * nxt) ;
}

bool check(int x , int y)
{
	int idx = lower_bound(v.begin() , v.end() , x - y) - v.begin() ;
	idx-- ;
	idx = max(idx , 0) ;
	return (query(1 , 0 , n , 0 , idx) <= x + y) ;
}

int solve(int x)
{
	int l = 0 , r = 1e8 ;
	int ans = -1 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(check(x , mid))
			ans = mid , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return ans ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k>>q ;
	for(int i = 0 ; i < n ; ++i)
	{
		int x , t , a , b ;
		cin>>x>>t>>a>>b ;
		queries.push_back({a , x , t , 0}) ;
		queries.push_back({b+1 , x , t , -1}) ;
		v.push_back(x) ;
	}
	for(int i = 0 ; i < q ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		queries.push_back({y , x , i , 1}) ;
	}
	v.push_back(0) ;
	sort(v.begin() , v.end()) ;
	v.erase(unique(v.begin() , v.end()) , v.end()) ;
	sort(queries.begin() , queries.end() , cmp) ;
	for(int i = 1 ; i <= k ; ++i)
		s[i].insert(0) , s[i].insert(inf) , update(1 , 0 , n , 0 , inf) ;
	for(auto &a : queries)
	{
		if(a[3] == 0)
			Add(a[1] , a[2]) ;
		else if(a[3] == -1)
			Erase(a[1] , a[2]) ;
		else
			ans[a[2]] = solve(a[1]) ;
	}
	for(int i = 0 ; i < q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70724 KB Output is correct
2 Correct 38 ms 70768 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 39 ms 70648 KB Output is correct
5 Correct 46 ms 70812 KB Output is correct
6 Correct 46 ms 70772 KB Output is correct
7 Correct 45 ms 70808 KB Output is correct
8 Correct 40 ms 70832 KB Output is correct
9 Correct 40 ms 70880 KB Output is correct
10 Correct 43 ms 70844 KB Output is correct
11 Correct 40 ms 70808 KB Output is correct
12 Correct 40 ms 70772 KB Output is correct
13 Correct 40 ms 70736 KB Output is correct
14 Correct 41 ms 70784 KB Output is correct
15 Correct 40 ms 70840 KB Output is correct
16 Correct 41 ms 70860 KB Output is correct
17 Correct 41 ms 70836 KB Output is correct
18 Correct 41 ms 70840 KB Output is correct
19 Correct 41 ms 70848 KB Output is correct
20 Correct 41 ms 70772 KB Output is correct
21 Correct 39 ms 70828 KB Output is correct
22 Correct 40 ms 70836 KB Output is correct
23 Correct 41 ms 70812 KB Output is correct
24 Correct 43 ms 70752 KB Output is correct
25 Correct 41 ms 70820 KB Output is correct
26 Correct 40 ms 70860 KB Output is correct
27 Correct 41 ms 70732 KB Output is correct
28 Correct 41 ms 70784 KB Output is correct
29 Correct 40 ms 70820 KB Output is correct
30 Correct 40 ms 70820 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70724 KB Output is correct
2 Correct 38 ms 70768 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 39 ms 70648 KB Output is correct
5 Correct 46 ms 70812 KB Output is correct
6 Correct 46 ms 70772 KB Output is correct
7 Correct 45 ms 70808 KB Output is correct
8 Correct 40 ms 70832 KB Output is correct
9 Correct 40 ms 70880 KB Output is correct
10 Correct 43 ms 70844 KB Output is correct
11 Correct 40 ms 70808 KB Output is correct
12 Correct 40 ms 70772 KB Output is correct
13 Correct 40 ms 70736 KB Output is correct
14 Correct 41 ms 70784 KB Output is correct
15 Correct 40 ms 70840 KB Output is correct
16 Correct 41 ms 70860 KB Output is correct
17 Correct 41 ms 70836 KB Output is correct
18 Correct 41 ms 70840 KB Output is correct
19 Correct 41 ms 70848 KB Output is correct
20 Correct 41 ms 70772 KB Output is correct
21 Correct 39 ms 70828 KB Output is correct
22 Correct 40 ms 70836 KB Output is correct
23 Correct 41 ms 70812 KB Output is correct
24 Correct 43 ms 70752 KB Output is correct
25 Correct 41 ms 70820 KB Output is correct
26 Correct 40 ms 70860 KB Output is correct
27 Correct 41 ms 70732 KB Output is correct
28 Correct 41 ms 70784 KB Output is correct
29 Correct 40 ms 70820 KB Output is correct
30 Correct 40 ms 70820 KB Output is correct
31 Correct 639 ms 80708 KB Output is correct
32 Correct 438 ms 76492 KB Output is correct
33 Correct 681 ms 77060 KB Output is correct
34 Correct 628 ms 77260 KB Output is correct
35 Correct 677 ms 80632 KB Output is correct
36 Correct 667 ms 80560 KB Output is correct
37 Correct 605 ms 75432 KB Output is correct
38 Correct 585 ms 75332 KB Output is correct
39 Correct 530 ms 75348 KB Output is correct
40 Correct 564 ms 75328 KB Output is correct
41 Correct 507 ms 75380 KB Output is correct
42 Correct 468 ms 75324 KB Output is correct
43 Correct 343 ms 80248 KB Output is correct
44 Correct 485 ms 75356 KB Output is correct
45 Correct 482 ms 75380 KB Output is correct
46 Correct 507 ms 75372 KB Output is correct
47 Correct 429 ms 75348 KB Output is correct
48 Correct 441 ms 75352 KB Output is correct
49 Correct 477 ms 75352 KB Output is correct
50 Correct 455 ms 75352 KB Output is correct
51 Correct 488 ms 75352 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3406 ms 130648 KB Output is correct
2 Correct 4131 ms 121068 KB Output is correct
3 Correct 3505 ms 164592 KB Output is correct
4 Correct 3504 ms 136272 KB Output is correct
5 Correct 4116 ms 120528 KB Output is correct
6 Correct 4075 ms 120904 KB Output is correct
7 Correct 3332 ms 164436 KB Output is correct
8 Correct 3045 ms 136300 KB Output is correct
9 Correct 2989 ms 126420 KB Output is correct
10 Correct 3639 ms 121588 KB Output is correct
11 Correct 2879 ms 120452 KB Output is correct
12 Correct 2898 ms 121460 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3814 ms 122648 KB Output is correct
2 Correct 2112 ms 115996 KB Output is correct
3 Correct 4285 ms 121124 KB Output is correct
4 Correct 3643 ms 176192 KB Output is correct
5 Correct 3380 ms 142364 KB Output is correct
6 Correct 3482 ms 147804 KB Output is correct
7 Correct 4344 ms 132956 KB Output is correct
8 Correct 4304 ms 133204 KB Output is correct
9 Correct 3659 ms 177380 KB Output is correct
10 Correct 3300 ms 145656 KB Output is correct
11 Correct 3395 ms 137252 KB Output is correct
12 Correct 4043 ms 134248 KB Output is correct
13 Correct 2733 ms 131636 KB Output is correct
14 Correct 2719 ms 130884 KB Output is correct
15 Correct 2972 ms 132796 KB Output is correct
16 Correct 3165 ms 133928 KB Output is correct
17 Correct 3129 ms 132108 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70724 KB Output is correct
2 Correct 38 ms 70768 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 39 ms 70648 KB Output is correct
5 Correct 46 ms 70812 KB Output is correct
6 Correct 46 ms 70772 KB Output is correct
7 Correct 45 ms 70808 KB Output is correct
8 Correct 40 ms 70832 KB Output is correct
9 Correct 40 ms 70880 KB Output is correct
10 Correct 43 ms 70844 KB Output is correct
11 Correct 40 ms 70808 KB Output is correct
12 Correct 40 ms 70772 KB Output is correct
13 Correct 40 ms 70736 KB Output is correct
14 Correct 41 ms 70784 KB Output is correct
15 Correct 40 ms 70840 KB Output is correct
16 Correct 41 ms 70860 KB Output is correct
17 Correct 41 ms 70836 KB Output is correct
18 Correct 41 ms 70840 KB Output is correct
19 Correct 41 ms 70848 KB Output is correct
20 Correct 41 ms 70772 KB Output is correct
21 Correct 39 ms 70828 KB Output is correct
22 Correct 40 ms 70836 KB Output is correct
23 Correct 41 ms 70812 KB Output is correct
24 Correct 43 ms 70752 KB Output is correct
25 Correct 41 ms 70820 KB Output is correct
26 Correct 40 ms 70860 KB Output is correct
27 Correct 41 ms 70732 KB Output is correct
28 Correct 41 ms 70784 KB Output is correct
29 Correct 40 ms 70820 KB Output is correct
30 Correct 40 ms 70820 KB Output is correct
31 Correct 639 ms 80708 KB Output is correct
32 Correct 438 ms 76492 KB Output is correct
33 Correct 681 ms 77060 KB Output is correct
34 Correct 628 ms 77260 KB Output is correct
35 Correct 677 ms 80632 KB Output is correct
36 Correct 667 ms 80560 KB Output is correct
37 Correct 605 ms 75432 KB Output is correct
38 Correct 585 ms 75332 KB Output is correct
39 Correct 530 ms 75348 KB Output is correct
40 Correct 564 ms 75328 KB Output is correct
41 Correct 507 ms 75380 KB Output is correct
42 Correct 468 ms 75324 KB Output is correct
43 Correct 343 ms 80248 KB Output is correct
44 Correct 485 ms 75356 KB Output is correct
45 Correct 482 ms 75380 KB Output is correct
46 Correct 507 ms 75372 KB Output is correct
47 Correct 429 ms 75348 KB Output is correct
48 Correct 441 ms 75352 KB Output is correct
49 Correct 477 ms 75352 KB Output is correct
50 Correct 455 ms 75352 KB Output is correct
51 Correct 488 ms 75352 KB Output is correct
52 Correct 608 ms 88808 KB Output is correct
53 Correct 581 ms 85396 KB Output is correct
54 Correct 565 ms 83288 KB Output is correct
55 Correct 524 ms 79820 KB Output is correct
56 Correct 547 ms 82252 KB Output is correct
57 Correct 516 ms 76620 KB Output is correct
58 Correct 530 ms 79768 KB Output is correct
59 Correct 547 ms 81972 KB Output is correct
60 Correct 523 ms 76492 KB Output is correct
61 Correct 416 ms 88700 KB Output is correct
62 Correct 627 ms 89444 KB Output is correct
63 Correct 629 ms 84288 KB Output is correct
64 Correct 560 ms 82048 KB Output is correct
65 Correct 511 ms 77648 KB Output is correct
66 Correct 487 ms 75984 KB Output is correct
67 Correct 401 ms 76816 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70724 KB Output is correct
2 Correct 38 ms 70768 KB Output is correct
3 Correct 38 ms 70732 KB Output is correct
4 Correct 39 ms 70648 KB Output is correct
5 Correct 46 ms 70812 KB Output is correct
6 Correct 46 ms 70772 KB Output is correct
7 Correct 45 ms 70808 KB Output is correct
8 Correct 40 ms 70832 KB Output is correct
9 Correct 40 ms 70880 KB Output is correct
10 Correct 43 ms 70844 KB Output is correct
11 Correct 40 ms 70808 KB Output is correct
12 Correct 40 ms 70772 KB Output is correct
13 Correct 40 ms 70736 KB Output is correct
14 Correct 41 ms 70784 KB Output is correct
15 Correct 40 ms 70840 KB Output is correct
16 Correct 41 ms 70860 KB Output is correct
17 Correct 41 ms 70836 KB Output is correct
18 Correct 41 ms 70840 KB Output is correct
19 Correct 41 ms 70848 KB Output is correct
20 Correct 41 ms 70772 KB Output is correct
21 Correct 39 ms 70828 KB Output is correct
22 Correct 40 ms 70836 KB Output is correct
23 Correct 41 ms 70812 KB Output is correct
24 Correct 43 ms 70752 KB Output is correct
25 Correct 41 ms 70820 KB Output is correct
26 Correct 40 ms 70860 KB Output is correct
27 Correct 41 ms 70732 KB Output is correct
28 Correct 41 ms 70784 KB Output is correct
29 Correct 40 ms 70820 KB Output is correct
30 Correct 40 ms 70820 KB Output is correct
31 Correct 639 ms 80708 KB Output is correct
32 Correct 438 ms 76492 KB Output is correct
33 Correct 681 ms 77060 KB Output is correct
34 Correct 628 ms 77260 KB Output is correct
35 Correct 677 ms 80632 KB Output is correct
36 Correct 667 ms 80560 KB Output is correct
37 Correct 605 ms 75432 KB Output is correct
38 Correct 585 ms 75332 KB Output is correct
39 Correct 530 ms 75348 KB Output is correct
40 Correct 564 ms 75328 KB Output is correct
41 Correct 507 ms 75380 KB Output is correct
42 Correct 468 ms 75324 KB Output is correct
43 Correct 343 ms 80248 KB Output is correct
44 Correct 485 ms 75356 KB Output is correct
45 Correct 482 ms 75380 KB Output is correct
46 Correct 507 ms 75372 KB Output is correct
47 Correct 429 ms 75348 KB Output is correct
48 Correct 441 ms 75352 KB Output is correct
49 Correct 477 ms 75352 KB Output is correct
50 Correct 455 ms 75352 KB Output is correct
51 Correct 488 ms 75352 KB Output is correct
52 Correct 3406 ms 130648 KB Output is correct
53 Correct 4131 ms 121068 KB Output is correct
54 Correct 3505 ms 164592 KB Output is correct
55 Correct 3504 ms 136272 KB Output is correct
56 Correct 4116 ms 120528 KB Output is correct
57 Correct 4075 ms 120904 KB Output is correct
58 Correct 3332 ms 164436 KB Output is correct
59 Correct 3045 ms 136300 KB Output is correct
60 Correct 2989 ms 126420 KB Output is correct
61 Correct 3639 ms 121588 KB Output is correct
62 Correct 2879 ms 120452 KB Output is correct
63 Correct 2898 ms 121460 KB Output is correct
64 Correct 3814 ms 122648 KB Output is correct
65 Correct 2112 ms 115996 KB Output is correct
66 Correct 4285 ms 121124 KB Output is correct
67 Correct 3643 ms 176192 KB Output is correct
68 Correct 3380 ms 142364 KB Output is correct
69 Correct 3482 ms 147804 KB Output is correct
70 Correct 4344 ms 132956 KB Output is correct
71 Correct 4304 ms 133204 KB Output is correct
72 Correct 3659 ms 177380 KB Output is correct
73 Correct 3300 ms 145656 KB Output is correct
74 Correct 3395 ms 137252 KB Output is correct
75 Correct 4043 ms 134248 KB Output is correct
76 Correct 2733 ms 131636 KB Output is correct
77 Correct 2719 ms 130884 KB Output is correct
78 Correct 2972 ms 132796 KB Output is correct
79 Correct 3165 ms 133928 KB Output is correct
80 Correct 3129 ms 132108 KB Output is correct
81 Correct 608 ms 88808 KB Output is correct
82 Correct 581 ms 85396 KB Output is correct
83 Correct 565 ms 83288 KB Output is correct
84 Correct 524 ms 79820 KB Output is correct
85 Correct 547 ms 82252 KB Output is correct
86 Correct 516 ms 76620 KB Output is correct
87 Correct 530 ms 79768 KB Output is correct
88 Correct 547 ms 81972 KB Output is correct
89 Correct 523 ms 76492 KB Output is correct
90 Correct 416 ms 88700 KB Output is correct
91 Correct 627 ms 89444 KB Output is correct
92 Correct 629 ms 84288 KB Output is correct
93 Correct 560 ms 82048 KB Output is correct
94 Correct 511 ms 77648 KB Output is correct
95 Correct 487 ms 75984 KB Output is correct
96 Correct 401 ms 76816 KB Output is correct
97 Correct 3706 ms 178412 KB Output is correct
98 Correct 2132 ms 104428 KB Output is correct
99 Correct 4335 ms 117668 KB Output is correct
100 Correct 3937 ms 160356 KB Output is correct
101 Correct 3662 ms 149880 KB Output is correct
102 Correct 4502 ms 135496 KB Output is correct
103 Correct 3499 ms 109804 KB Output is correct
104 Correct 3537 ms 109452 KB Output is correct
105 Correct 3039 ms 109464 KB Output is correct
106 Correct 3134 ms 109008 KB Output is correct
107 Correct 3171 ms 133084 KB Output is correct
108 Correct 3365 ms 144748 KB Output is correct
109 Correct 3033 ms 116664 KB Output is correct
110 Correct 3200 ms 132472 KB Output is correct
111 Correct 3376 ms 144072 KB Output is correct
112 Correct 2954 ms 115916 KB Output is correct
113 Correct 2143 ms 172972 KB Output is correct
114 Correct 3813 ms 178784 KB Output is correct
115 Correct 3725 ms 152812 KB Output is correct
116 Correct 3737 ms 141400 KB Output is correct
117 Correct 3452 ms 119824 KB Output is correct
118 Correct 2896 ms 111040 KB Output is correct
119 Correct 2670 ms 105092 KB Output is correct
120 Correct 2204 ms 107092 KB Output is correct
121 Correct 2446 ms 108588 KB Output is correct
122 Correct 2444 ms 108304 KB Output is correct
123 Correct 2565 ms 109056 KB Output is correct
124 Correct 2609 ms 109576 KB Output is correct
125 Correct 2746 ms 109312 KB Output is correct
126 Correct 2597 ms 109640 KB Output is correct