oj.uz

Submission #157183

# Submission time Handle Problem Language Result Execution time Memory
157183 2019-10-10T02:40:43 Z puppies_and_rainbows Examination (JOI19_examination) C++14
2 / 100
 1711 ms 1048576 KB 
#include <bits/stdc++.h>
#define int long long
#define left dhusiad
#define right dusanan
using namespace std;

pair<int, int> a[100005], cursort[100005];
int it[400005], root[400005];
int it1[33000005], left[33000005], right[33000005];
vector<int> check[33000005];
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 823 ms 775380 KB Output is correct
2 Correct 731 ms 775308 KB Output is correct
3 Correct 726 ms 775452 KB Output is correct
4 Correct 725 ms 775348 KB Output is correct
5 Correct 728 ms 775388 KB Output is correct
6 Correct 728 ms 775428 KB Output is correct
7 Correct 846 ms 781280 KB Output is correct
8 Correct 824 ms 781524 KB Output is correct
9 Correct 779 ms 781312 KB Output is correct
10 Correct 840 ms 781308 KB Output is correct
11 Correct 769 ms 781260 KB Output is correct
12 Correct 767 ms 781168 KB Output is correct
13 Correct 770 ms 781384 KB Output is correct
14 Correct 772 ms 781332 KB Output is correct
15 Correct 774 ms 781280 KB Output is correct
16 Correct 760 ms 781448 KB Output is correct
17 Correct 764 ms 781464 KB Output is correct
18 Correct 839 ms 781356 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1711 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1711 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 775380 KB Output is correct
2 Correct 731 ms 775308 KB Output is correct
3 Correct 726 ms 775452 KB Output is correct
4 Correct 725 ms 775348 KB Output is correct
5 Correct 728 ms 775388 KB Output is correct
6 Correct 728 ms 775428 KB Output is correct
7 Correct 846 ms 781280 KB Output is correct
8 Correct 824 ms 781524 KB Output is correct
9 Correct 779 ms 781312 KB Output is correct
10 Correct 840 ms 781308 KB Output is correct
11 Correct 769 ms 781260 KB Output is correct
12 Correct 767 ms 781168 KB Output is correct
13 Correct 770 ms 781384 KB Output is correct
14 Correct 772 ms 781332 KB Output is correct
15 Correct 774 ms 781280 KB Output is correct
16 Correct 760 ms 781448 KB Output is correct
17 Correct 764 ms 781464 KB Output is correct
18 Correct 839 ms 781356 KB Output is correct
19 Runtime error 1711 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -