oj.uz

Submission #157189

# Submission time Handle Problem Language Result Execution time Memory
157189 2019-10-10T02:52:12 Z puppies_and_rainbows Examination (JOI19_examination) C++14
2 / 100
 1875 ms 839268 KB 
#include <bits/stdc++.h>
#define left dhusiad
#define right dusanan
using namespace std;

pair<int, int> a[1000005], cursort[1000005];
int it[1000005], root[1000005];
int it1[1000005], left[1000005], right[1000005];
vector<int> check[10000005];
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 250 ms 235284 KB Output is correct
2 Correct 227 ms 235324 KB Output is correct
3 Correct 227 ms 235256 KB Output is correct
4 Correct 282 ms 235160 KB Output is correct
5 Correct 227 ms 235256 KB Output is correct
6 Correct 240 ms 235256 KB Output is correct
7 Correct 269 ms 239244 KB Output is correct
8 Correct 270 ms 239268 KB Output is correct
9 Correct 266 ms 239224 KB Output is correct
10 Correct 265 ms 239196 KB Output is correct
11 Correct 259 ms 239172 KB Output is correct
12 Correct 268 ms 239180 KB Output is correct
13 Correct 264 ms 239216 KB Output is correct
14 Correct 304 ms 239224 KB Output is correct
15 Correct 265 ms 239324 KB Output is correct
16 Correct 298 ms 239096 KB Output is correct
17 Correct 260 ms 239352 KB Output is correct
18 Correct 249 ms 239096 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1875 ms 839268 KB Execution killed with signal 11 (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 1875 ms 839268 KB Execution killed with signal 11 (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 250 ms 235284 KB Output is correct
2 Correct 227 ms 235324 KB Output is correct
3 Correct 227 ms 235256 KB Output is correct
4 Correct 282 ms 235160 KB Output is correct
5 Correct 227 ms 235256 KB Output is correct
6 Correct 240 ms 235256 KB Output is correct
7 Correct 269 ms 239244 KB Output is correct
8 Correct 270 ms 239268 KB Output is correct
9 Correct 266 ms 239224 KB Output is correct
10 Correct 265 ms 239196 KB Output is correct
11 Correct 259 ms 239172 KB Output is correct
12 Correct 268 ms 239180 KB Output is correct
13 Correct 264 ms 239216 KB Output is correct
14 Correct 304 ms 239224 KB Output is correct
15 Correct 265 ms 239324 KB Output is correct
16 Correct 298 ms 239096 KB Output is correct
17 Correct 260 ms 239352 KB Output is correct
18 Correct 249 ms 239096 KB Output is correct
19 Runtime error 1875 ms 839268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -