oj.uz

Submission #126863

# Submission time Handle Problem Language Result Execution time Memory
126863 2019-07-08T14:25:39 Z mahmoudbadawy Examination (JOI19_examination) C++17
22 / 100
 3000 ms 151764 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops") 
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define F first
#define S second

using namespace std;
using namespace __gnu_pbds;

typedef tree<
pair<int,int>,
null_type,
less<pair<int,int> >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int N=1e5+5;

int read_int () {
	bool minus = false;
	int result = 0;
	char ch;
	ch = getchar();
	while (true) {
		if (ch == '-') break;
		if (ch >= '0' && ch <= '9') break;
		ch = getchar();
	}
	if (ch == '-') minus = true; else result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = (result<<3)+(result<<1) + (ch - '0');
	}
	if (minus)
		return -result;
	else
		return result;
}

ordered_set btree[4*N];
pair<int,int> arr[N];
pair<pair<int,int>, pair<int,int> > qs[N];
vector<int> cmp;
int ans[N];
int n,q;

int get(int x)
{
	return lower_bound(cmp.begin(),cmp.end(),x)-cmp.begin();
}

void add(int ind,int sm,int x,int node=1,int l=0,int r=cmp.size()-1)
{
	if(r<ind||l>ind) return;
	btree[node].insert({sm,x});
	if(l==r)
		return;
	int mid=(l+r)/2;
	add(ind,sm,x,node<<1,l,mid);
	add(ind,sm,x,(node<<1)+1,mid+1,r);
}

void rem(int ind,int sm,int x,int node=1,int l=0,int r=cmp.size()-1)
{
	if(r<ind||l>ind) return;
	btree[node].erase({sm,x});
	if(l==r)
		return;
	int mid=(l+r)/2;
	rem(ind,sm,x,node<<1,l,mid);
	rem(ind,sm,x,(node<<1)+1,mid+1,r);
}

int query(int ql,int qr,int val,int node=1,int l=0,int r=cmp.size()-1)
{
	if(r<ql||qr<l) return 0;
	if(ql<=l&&r<=qr)
	{
		return btree[node].size()-btree[node].order_of_key({val,-1});
	}
	int mid=(l+r)/2;
	return query(ql,qr,val,node<<1,l,mid)+query(ql,qr,val,(node<<1)+1,mid+1,r);
}

int main()
{
	//scanf("%d %d",&n,&q);
	n=read_int(); q=read_int();
	for(int i=0;i<n;i++)
	{
		arr[i].F=read_int(); arr[i].S=read_int();
		//scanf("%d %d",&arr[i].F,&arr[i].S);
		cmp.push_back(arr[i].S);
	}
	for(int i=0;i<q;i++)
	{
		//scanf("%d %d %d",&qs[i].F.F,&qs[i].F.S,&qs[i].S.F);
		qs[i].F.F=read_int(); qs[i].F.S=read_int();
		qs[i].S.F=read_int();
		qs[i].S.S=i;
		cmp.push_back(qs[i].F.S);
	}
	sort(cmp.begin(),cmp.end());
	cmp.erase(unique(cmp.begin(),cmp.end()),cmp.end());
	sort(arr,arr+n);
	sort(qs,qs+q);
	for(int i=0;i<n;i++)
	{
		add(get(arr[i].S),arr[i].F+arr[i].S,i);
	}
	int curs=0;
	for(int i=0;i<q;i++)
	{
		while(arr[curs].F<qs[i].F.F)
		{
			rem(get(arr[curs].S),arr[curs].F+arr[curs].S,curs);
			curs++;
		}
		/*cout << "ON " << qs[i].F.F << " " << curs << endl;
		for(int i=0;i<btree[1].size();i++)
		{
			auto x=*btree[1].find_by_order(i);
			cout << x.F << " " << x.S << endl;
		}*/
		ans[qs[i].S.S]=query(get(qs[i].F.S),cmp.size()-1,qs[i].S.F);
	}
	for(int i=0;i<q;i++)
		printf("%d\n",ans[i]);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 37880 KB Output is correct
2 Correct 50 ms 37880 KB Output is correct
3 Correct 55 ms 37880 KB Output is correct
4 Correct 56 ms 37880 KB Output is correct
5 Correct 117 ms 38008 KB Output is correct
6 Correct 116 ms 37880 KB Output is correct
7 Correct 228 ms 40748 KB Output is correct
8 Correct 225 ms 40696 KB Output is correct
9 Correct 232 ms 40696 KB Output is correct
10 Correct 114 ms 39160 KB Output is correct
11 Correct 76 ms 40804 KB Output is correct
12 Correct 61 ms 38904 KB Output is correct
13 Correct 225 ms 40696 KB Output is correct
14 Correct 231 ms 40696 KB Output is correct
15 Correct 223 ms 40696 KB Output is correct
16 Correct 74 ms 40700 KB Output is correct
17 Correct 56 ms 38520 KB Output is correct
18 Correct 58 ms 38648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2763 ms 151576 KB Output is correct
2 Correct 2843 ms 151764 KB Output is correct
3 Correct 2670 ms 151512 KB Output is correct
4 Correct 439 ms 70512 KB Output is correct
5 Correct 1318 ms 151464 KB Output is correct
6 Correct 446 ms 70476 KB Output is correct
7 Correct 2203 ms 151676 KB Output is correct
8 Correct 2614 ms 148780 KB Output is correct
9 Correct 2106 ms 148812 KB Output is correct
10 Correct 876 ms 151324 KB Output is correct
11 Correct 343 ms 54480 KB Output is correct
12 Correct 399 ms 60524 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2763 ms 151576 KB Output is correct
2 Correct 2843 ms 151764 KB Output is correct
3 Correct 2670 ms 151512 KB Output is correct
4 Correct 439 ms 70512 KB Output is correct
5 Correct 1318 ms 151464 KB Output is correct
6 Correct 446 ms 70476 KB Output is correct
7 Correct 2203 ms 151676 KB Output is correct
8 Correct 2614 ms 148780 KB Output is correct
9 Correct 2106 ms 148812 KB Output is correct
10 Correct 876 ms 151324 KB Output is correct
11 Correct 343 ms 54480 KB Output is correct
12 Correct 399 ms 60524 KB Output is correct
13 Execution timed out 3035 ms 150984 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 37880 KB Output is correct
2 Correct 50 ms 37880 KB Output is correct
3 Correct 55 ms 37880 KB Output is correct
4 Correct 56 ms 37880 KB Output is correct
5 Correct 117 ms 38008 KB Output is correct
6 Correct 116 ms 37880 KB Output is correct
7 Correct 228 ms 40748 KB Output is correct
8 Correct 225 ms 40696 KB Output is correct
9 Correct 232 ms 40696 KB Output is correct
10 Correct 114 ms 39160 KB Output is correct
11 Correct 76 ms 40804 KB Output is correct
12 Correct 61 ms 38904 KB Output is correct
13 Correct 225 ms 40696 KB Output is correct
14 Correct 231 ms 40696 KB Output is correct
15 Correct 223 ms 40696 KB Output is correct
16 Correct 74 ms 40700 KB Output is correct
17 Correct 56 ms 38520 KB Output is correct
18 Correct 58 ms 38648 KB Output is correct
19 Correct 2763 ms 151576 KB Output is correct
20 Correct 2843 ms 151764 KB Output is correct
21 Correct 2670 ms 151512 KB Output is correct
22 Correct 439 ms 70512 KB Output is correct
23 Correct 1318 ms 151464 KB Output is correct
24 Correct 446 ms 70476 KB Output is correct
25 Correct 2203 ms 151676 KB Output is correct
26 Correct 2614 ms 148780 KB Output is correct
27 Correct 2106 ms 148812 KB Output is correct
28 Correct 876 ms 151324 KB Output is correct
29 Correct 343 ms 54480 KB Output is correct
30 Correct 399 ms 60524 KB Output is correct
31 Execution timed out 3035 ms 150984 KB Time limit exceeded
32 Halted 0 ms 0 KB -