oj.uz

Submission #126885

# Submission time Handle Problem Language Result Execution time Memory
126885 2019-07-08T14:54:16 Z mahmoudbadawy Examination (JOI19_examination) C++17
22 / 100
 3000 ms 153976 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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 51 ms 37880 KB Output is correct
3 Correct 50 ms 37880 KB Output is correct
4 Correct 51 ms 37880 KB Output is correct
5 Correct 117 ms 37880 KB Output is correct
6 Correct 116 ms 37880 KB Output is correct
7 Correct 224 ms 40796 KB Output is correct
8 Correct 229 ms 40780 KB Output is correct
9 Correct 227 ms 40696 KB Output is correct
10 Correct 114 ms 39032 KB Output is correct
11 Correct 71 ms 40696 KB Output is correct
12 Correct 58 ms 38904 KB Output is correct
13 Correct 224 ms 40740 KB Output is correct
14 Correct 224 ms 40668 KB Output is correct
15 Correct 225 ms 40824 KB Output is correct
16 Correct 74 ms 40824 KB Output is correct
17 Correct 55 ms 38648 KB Output is correct
18 Correct 57 ms 38648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2665 ms 153976 KB Output is correct
2 Correct 2774 ms 153836 KB Output is correct
3 Correct 2884 ms 153904 KB Output is correct
4 Correct 454 ms 72040 KB Output is correct
5 Correct 1324 ms 153068 KB Output is correct
6 Correct 397 ms 71508 KB Output is correct
7 Correct 2218 ms 153648 KB Output is correct
8 Correct 2704 ms 149968 KB Output is correct
9 Correct 2041 ms 150092 KB Output is correct
10 Correct 869 ms 152500 KB Output is correct
11 Correct 353 ms 55672 KB Output is correct
12 Correct 430 ms 61160 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2665 ms 153976 KB Output is correct
2 Correct 2774 ms 153836 KB Output is correct
3 Correct 2884 ms 153904 KB Output is correct
4 Correct 454 ms 72040 KB Output is correct
5 Correct 1324 ms 153068 KB Output is correct
6 Correct 397 ms 71508 KB Output is correct
7 Correct 2218 ms 153648 KB Output is correct
8 Correct 2704 ms 149968 KB Output is correct
9 Correct 2041 ms 150092 KB Output is correct
10 Correct 869 ms 152500 KB Output is correct
11 Correct 353 ms 55672 KB Output is correct
12 Correct 430 ms 61160 KB Output is correct
13 Execution timed out 3052 ms 152388 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 51 ms 37880 KB Output is correct
3 Correct 50 ms 37880 KB Output is correct
4 Correct 51 ms 37880 KB Output is correct
5 Correct 117 ms 37880 KB Output is correct
6 Correct 116 ms 37880 KB Output is correct
7 Correct 224 ms 40796 KB Output is correct
8 Correct 229 ms 40780 KB Output is correct
9 Correct 227 ms 40696 KB Output is correct
10 Correct 114 ms 39032 KB Output is correct
11 Correct 71 ms 40696 KB Output is correct
12 Correct 58 ms 38904 KB Output is correct
13 Correct 224 ms 40740 KB Output is correct
14 Correct 224 ms 40668 KB Output is correct
15 Correct 225 ms 40824 KB Output is correct
16 Correct 74 ms 40824 KB Output is correct
17 Correct 55 ms 38648 KB Output is correct
18 Correct 57 ms 38648 KB Output is correct
19 Correct 2665 ms 153976 KB Output is correct
20 Correct 2774 ms 153836 KB Output is correct
21 Correct 2884 ms 153904 KB Output is correct
22 Correct 454 ms 72040 KB Output is correct
23 Correct 1324 ms 153068 KB Output is correct
24 Correct 397 ms 71508 KB Output is correct
25 Correct 2218 ms 153648 KB Output is correct
26 Correct 2704 ms 149968 KB Output is correct
27 Correct 2041 ms 150092 KB Output is correct
28 Correct 869 ms 152500 KB Output is correct
29 Correct 353 ms 55672 KB Output is correct
30 Correct 430 ms 61160 KB Output is correct
31 Execution timed out 3052 ms 152388 KB Time limit exceeded
32 Halted 0 ms 0 KB -