oj.uz

Submission #157190

# Submission time Handle Problem Language Result Execution time Memory
157190 2019-10-10T02:54:04 Z puppies_and_rainbows Examination (JOI19_examination) C++14
43 / 100
 3000 ms 676492 KB 
#include <bits/stdc++.h>
#define left dhusiad
#define right dusanan
using namespace std;

pair<int, int> a[1000005], cursort[1000005];
int it[400005], root[400005];
int it1[20000005], left[20000005], right[20000005];
vector<int> check[20000005];
int cntnode=0, ans, ans1;
int n;

int itgen(int l, int r)
{
	if(l>r) return 0;
	cntnode++;
	int id=cntnode;
	for(int i=l; i<=r; i++)
	{
		check[id].push_back(cursort[i].second);
	}
	it1[id]=cursort[r].first;
	sort(check[id].begin(), check[id].end());
	int mid=(l+r)/2;
	if(l==r) return id;
	left[id]=itgen(l, mid);
	right[id]=itgen(mid+1, r);
	return id;
}

void build_tree(int id, int l, int r)
{
	// cout<<"DEBUG "<<l<<" "<<r<<endl;
	for(int i=l; i<=r; i++)
	{
		cursort[i]={a[i].second, a[i].first+a[i].second};
		// cout<<cursort[i].first<<" "<<cursort[i].second<<endl;
	}
	// cout<<endl;
	sort(cursort+l, cursort+r+1);
	// for(int i=l; i<=r; i++)
	// {
	// 	cout<<cursort[i].first<<" "<<cursort[i].second<<endl;
	// }
	// cout<<endl;
	root[id]=itgen(l, r);
	if(l==r) it[id]=a[l].first;
	else
	{
		int mid=(l+r)/2;
		build_tree(id*2, l, mid);
		build_tree(id*2+1, mid+1, r);
		it[id]=max(it[id*2], it[id*2+1]);
	}
}

void solvehave(int ok, int y, int z, int l, int r)
{
	// cout<<l<<" "<<r<<" "<<ans1<<endl;
	int id=root[ok];
	while(l<r)
	{
		int mid=(l+r)/2;
		if(it1[left[id]]>=y)
		{
			ans1+=(int)(check[right[id]].end()-lower_bound(check[right[id]].begin(), check[right[id]].end(), z));
			id=left[id];
			r=mid;
		}
		else
		{
			id=right[id];
			l=mid+1;
		}
	}
	if(it1[id]>=y&&check[id][0]>=z) ans1++;
	// cout<<ans1<<endl;
}

void solvefail(int id, int z)
{
	return;
	ans+=check[root[id]].end()-lower_bound(check[root[id]].begin(), check[root[id]].end(), z);
}

bool checkk(int id, int x, int y, int z)
{
	if(a[id].first>=x&&a[id].second>=y&&a[id].first+a[id].second>=z) return true;
	return false;
}

int solve(int x, int y, int z)
{
	ans=0, ans1=0;
	int id=1, l=1, r=n;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(it[id*2]>=x)
		{
			solvehave(id*2+1, y, z, mid+1, r);
			id*=2;
			r=mid;
		}
		else
		{
			solvefail(id*2, z);
			id=id*2+1;
			l=mid+1;
		}
	}
	if(checkk(l, x, y, z))
	{
		ans++;
	}
	return ans+ans1;
}

signed main()
{
	int q;
	cin>>n>>q;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i].first>>a[i].second;
	}
	sort(a+1, a+n+1);
	build_tree(1, 1, n);
	// cout<<1<<endl;
	// return 0;
	int x, y, z;
	for(int i=1; i<=q; i++)
	{
		cin>>x>>y>>z;
		cout<<solve(x, y, z)<<endl;
	}
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 470136 KB Output is correct
2 Correct 439 ms 470088 KB Output is correct
3 Correct 438 ms 470136 KB Output is correct
4 Correct 443 ms 470076 KB Output is correct
5 Correct 438 ms 470140 KB Output is correct
6 Correct 433 ms 470024 KB Output is correct
7 Correct 478 ms 473976 KB Output is correct
8 Correct 482 ms 473992 KB Output is correct
9 Correct 482 ms 473976 KB Output is correct
10 Correct 478 ms 474036 KB Output is correct
11 Correct 520 ms 474048 KB Output is correct
12 Correct 474 ms 473836 KB Output is correct
13 Correct 535 ms 474060 KB Output is correct
14 Correct 481 ms 473980 KB Output is correct
15 Correct 479 ms 473976 KB Output is correct
16 Correct 469 ms 473816 KB Output is correct
17 Correct 480 ms 473872 KB Output is correct
18 Correct 460 ms 473848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2719 ms 671496 KB Output is correct
2 Correct 2692 ms 674108 KB Output is correct
3 Correct 2689 ms 674164 KB Output is correct
4 Correct 2446 ms 673392 KB Output is correct
5 Correct 1986 ms 673404 KB Output is correct
6 Correct 1788 ms 672488 KB Output is correct
7 Correct 2652 ms 674064 KB Output is correct
8 Correct 2513 ms 673936 KB Output is correct
9 Correct 2438 ms 673824 KB Output is correct
10 Correct 1763 ms 673072 KB Output is correct
11 Correct 1956 ms 673184 KB Output is correct
12 Correct 1659 ms 672140 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2719 ms 671496 KB Output is correct
2 Correct 2692 ms 674108 KB Output is correct
3 Correct 2689 ms 674164 KB Output is correct
4 Correct 2446 ms 673392 KB Output is correct
5 Correct 1986 ms 673404 KB Output is correct
6 Correct 1788 ms 672488 KB Output is correct
7 Correct 2652 ms 674064 KB Output is correct
8 Correct 2513 ms 673936 KB Output is correct
9 Correct 2438 ms 673824 KB Output is correct
10 Correct 1763 ms 673072 KB Output is correct
11 Correct 1956 ms 673184 KB Output is correct
12 Correct 1659 ms 672140 KB Output is correct
13 Correct 2815 ms 674484 KB Output is correct
14 Correct 2710 ms 674460 KB Output is correct
15 Correct 2861 ms 673856 KB Output is correct
16 Correct 2681 ms 673572 KB Output is correct
17 Correct 2086 ms 673616 KB Output is correct
18 Correct 1821 ms 672596 KB Output is correct
19 Correct 2928 ms 674324 KB Output is correct
20 Correct 2801 ms 674436 KB Output is correct
21 Correct 2747 ms 674284 KB Output is correct
22 Correct 1773 ms 673084 KB Output is correct
23 Correct 2128 ms 673160 KB Output is correct
24 Correct 1651 ms 672116 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 470136 KB Output is correct
2 Correct 439 ms 470088 KB Output is correct
3 Correct 438 ms 470136 KB Output is correct
4 Correct 443 ms 470076 KB Output is correct
5 Correct 438 ms 470140 KB Output is correct
6 Correct 433 ms 470024 KB Output is correct
7 Correct 478 ms 473976 KB Output is correct
8 Correct 482 ms 473992 KB Output is correct
9 Correct 482 ms 473976 KB Output is correct
10 Correct 478 ms 474036 KB Output is correct
11 Correct 520 ms 474048 KB Output is correct
12 Correct 474 ms 473836 KB Output is correct
13 Correct 535 ms 474060 KB Output is correct
14 Correct 481 ms 473980 KB Output is correct
15 Correct 479 ms 473976 KB Output is correct
16 Correct 469 ms 473816 KB Output is correct
17 Correct 480 ms 473872 KB Output is correct
18 Correct 460 ms 473848 KB Output is correct
19 Correct 2719 ms 671496 KB Output is correct
20 Correct 2692 ms 674108 KB Output is correct
21 Correct 2689 ms 674164 KB Output is correct
22 Correct 2446 ms 673392 KB Output is correct
23 Correct 1986 ms 673404 KB Output is correct
24 Correct 1788 ms 672488 KB Output is correct
25 Correct 2652 ms 674064 KB Output is correct
26 Correct 2513 ms 673936 KB Output is correct
27 Correct 2438 ms 673824 KB Output is correct
28 Correct 1763 ms 673072 KB Output is correct
29 Correct 1956 ms 673184 KB Output is correct
30 Correct 1659 ms 672140 KB Output is correct
31 Correct 2815 ms 674484 KB Output is correct
32 Correct 2710 ms 674460 KB Output is correct
33 Correct 2861 ms 673856 KB Output is correct
34 Correct 2681 ms 673572 KB Output is correct
35 Correct 2086 ms 673616 KB Output is correct
36 Correct 1821 ms 672596 KB Output is correct
37 Correct 2928 ms 674324 KB Output is correct
38 Correct 2801 ms 674436 KB Output is correct
39 Correct 2747 ms 674284 KB Output is correct
40 Correct 1773 ms 673084 KB Output is correct
41 Correct 2128 ms 673160 KB Output is correct
42 Correct 1651 ms 672116 KB Output is correct
43 Execution timed out 3028 ms 676492 KB Time limit exceeded
44 Halted 0 ms 0 KB -