oj.uz

Submission #126871

# Submission time Handle Problem Language Result Execution time Memory
126871 2019-07-08T14:34:12 Z mahmoudbadawy Examination (JOI19_examination) C++14
22 / 100
 3000 ms 151692 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 49 ms 37880 KB Output is correct
3 Correct 50 ms 37904 KB Output is correct
4 Correct 49 ms 37880 KB Output is correct
5 Correct 122 ms 37988 KB Output is correct
6 Correct 122 ms 37880 KB Output is correct
7 Correct 242 ms 40824 KB Output is correct
8 Correct 243 ms 40728 KB Output is correct
9 Correct 242 ms 40696 KB Output is correct
10 Correct 121 ms 38904 KB Output is correct
11 Correct 69 ms 40696 KB Output is correct
12 Correct 57 ms 38908 KB Output is correct
13 Correct 241 ms 40824 KB Output is correct
14 Correct 240 ms 40744 KB Output is correct
15 Correct 239 ms 40796 KB Output is correct
16 Correct 74 ms 40824 KB Output is correct
17 Correct 56 ms 38520 KB Output is correct
18 Correct 57 ms 38584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2767 ms 151488 KB Output is correct
2 Correct 2730 ms 151532 KB Output is correct
3 Correct 2769 ms 151476 KB Output is correct
4 Correct 440 ms 70468 KB Output is correct
5 Correct 1301 ms 151564 KB Output is correct
6 Correct 416 ms 70592 KB Output is correct
7 Correct 2239 ms 151692 KB Output is correct
8 Correct 2769 ms 148868 KB Output is correct
9 Correct 2181 ms 148992 KB Output is correct
10 Correct 894 ms 151388 KB Output is correct
11 Correct 361 ms 54424 KB Output is correct
12 Correct 415 ms 60396 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2767 ms 151488 KB Output is correct
2 Correct 2730 ms 151532 KB Output is correct
3 Correct 2769 ms 151476 KB Output is correct
4 Correct 440 ms 70468 KB Output is correct
5 Correct 1301 ms 151564 KB Output is correct
6 Correct 416 ms 70592 KB Output is correct
7 Correct 2239 ms 151692 KB Output is correct
8 Correct 2769 ms 148868 KB Output is correct
9 Correct 2181 ms 148992 KB Output is correct
10 Correct 894 ms 151388 KB Output is correct
11 Correct 361 ms 54424 KB Output is correct
12 Correct 415 ms 60396 KB Output is correct
13 Execution timed out 3037 ms 151000 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 49 ms 37880 KB Output is correct
3 Correct 50 ms 37904 KB Output is correct
4 Correct 49 ms 37880 KB Output is correct
5 Correct 122 ms 37988 KB Output is correct
6 Correct 122 ms 37880 KB Output is correct
7 Correct 242 ms 40824 KB Output is correct
8 Correct 243 ms 40728 KB Output is correct
9 Correct 242 ms 40696 KB Output is correct
10 Correct 121 ms 38904 KB Output is correct
11 Correct 69 ms 40696 KB Output is correct
12 Correct 57 ms 38908 KB Output is correct
13 Correct 241 ms 40824 KB Output is correct
14 Correct 240 ms 40744 KB Output is correct
15 Correct 239 ms 40796 KB Output is correct
16 Correct 74 ms 40824 KB Output is correct
17 Correct 56 ms 38520 KB Output is correct
18 Correct 57 ms 38584 KB Output is correct
19 Correct 2767 ms 151488 KB Output is correct
20 Correct 2730 ms 151532 KB Output is correct
21 Correct 2769 ms 151476 KB Output is correct
22 Correct 440 ms 70468 KB Output is correct
23 Correct 1301 ms 151564 KB Output is correct
24 Correct 416 ms 70592 KB Output is correct
25 Correct 2239 ms 151692 KB Output is correct
26 Correct 2769 ms 148868 KB Output is correct
27 Correct 2181 ms 148992 KB Output is correct
28 Correct 894 ms 151388 KB Output is correct
29 Correct 361 ms 54424 KB Output is correct
30 Correct 415 ms 60396 KB Output is correct
31 Execution timed out 3037 ms 151000 KB Time limit exceeded
32 Halted 0 ms 0 KB -