oj.uz

Submission #126893

# Submission time Handle Problem Language Result Execution time Memory
126893 2019-07-08T15:00:02 Z mahmoudbadawy Examination (JOI19_examination) C++17
100 / 100
 2784 ms 201580 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*2*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);
	int curs=n-1;
	for(int i=q-1;i>=0;i--)
	{
		while(curs>=0&&arr[curs].F>=qs[i].F.F)
		{
			add(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 98 ms 75592 KB Output is correct
2 Correct 98 ms 75512 KB Output is correct
3 Correct 97 ms 75640 KB Output is correct
4 Correct 98 ms 75484 KB Output is correct
5 Correct 100 ms 75536 KB Output is correct
6 Correct 97 ms 75484 KB Output is correct
7 Correct 121 ms 78328 KB Output is correct
8 Correct 119 ms 78200 KB Output is correct
9 Correct 121 ms 78200 KB Output is correct
10 Correct 106 ms 76636 KB Output is correct
11 Correct 115 ms 78200 KB Output is correct
12 Correct 104 ms 76456 KB Output is correct
13 Correct 121 ms 78328 KB Output is correct
14 Correct 120 ms 78200 KB Output is correct
15 Correct 142 ms 78328 KB Output is correct
16 Correct 121 ms 78200 KB Output is correct
17 Correct 103 ms 76024 KB Output is correct
18 Correct 102 ms 76384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2525 ms 189312 KB Output is correct
2 Correct 2428 ms 189448 KB Output is correct
3 Correct 2423 ms 189236 KB Output is correct
4 Correct 501 ms 109108 KB Output is correct
5 Correct 1284 ms 190152 KB Output is correct
6 Correct 452 ms 108820 KB Output is correct
7 Correct 2609 ms 190488 KB Output is correct
8 Correct 2349 ms 188396 KB Output is correct
9 Correct 2291 ms 188344 KB Output is correct
10 Correct 1132 ms 190448 KB Output is correct
11 Correct 365 ms 93416 KB Output is correct
12 Correct 412 ms 99060 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2525 ms 189312 KB Output is correct
2 Correct 2428 ms 189448 KB Output is correct
3 Correct 2423 ms 189236 KB Output is correct
4 Correct 501 ms 109108 KB Output is correct
5 Correct 1284 ms 190152 KB Output is correct
6 Correct 452 ms 108820 KB Output is correct
7 Correct 2609 ms 190488 KB Output is correct
8 Correct 2349 ms 188396 KB Output is correct
9 Correct 2291 ms 188344 KB Output is correct
10 Correct 1132 ms 190448 KB Output is correct
11 Correct 365 ms 93416 KB Output is correct
12 Correct 412 ms 99060 KB Output is correct
13 Correct 2784 ms 191144 KB Output is correct
14 Correct 2528 ms 190064 KB Output is correct
15 Correct 2408 ms 190036 KB Output is correct
16 Correct 563 ms 109168 KB Output is correct
17 Correct 1282 ms 190192 KB Output is correct
18 Correct 458 ms 109076 KB Output is correct
19 Correct 2573 ms 190036 KB Output is correct
20 Correct 2618 ms 190100 KB Output is correct
21 Correct 2703 ms 189292 KB Output is correct
22 Correct 1055 ms 189936 KB Output is correct
23 Correct 368 ms 92820 KB Output is correct
24 Correct 412 ms 98992 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 75592 KB Output is correct
2 Correct 98 ms 75512 KB Output is correct
3 Correct 97 ms 75640 KB Output is correct
4 Correct 98 ms 75484 KB Output is correct
5 Correct 100 ms 75536 KB Output is correct
6 Correct 97 ms 75484 KB Output is correct
7 Correct 121 ms 78328 KB Output is correct
8 Correct 119 ms 78200 KB Output is correct
9 Correct 121 ms 78200 KB Output is correct
10 Correct 106 ms 76636 KB Output is correct
11 Correct 115 ms 78200 KB Output is correct
12 Correct 104 ms 76456 KB Output is correct
13 Correct 121 ms 78328 KB Output is correct
14 Correct 120 ms 78200 KB Output is correct
15 Correct 142 ms 78328 KB Output is correct
16 Correct 121 ms 78200 KB Output is correct
17 Correct 103 ms 76024 KB Output is correct
18 Correct 102 ms 76384 KB Output is correct
19 Correct 2525 ms 189312 KB Output is correct
20 Correct 2428 ms 189448 KB Output is correct
21 Correct 2423 ms 189236 KB Output is correct
22 Correct 501 ms 109108 KB Output is correct
23 Correct 1284 ms 190152 KB Output is correct
24 Correct 452 ms 108820 KB Output is correct
25 Correct 2609 ms 190488 KB Output is correct
26 Correct 2349 ms 188396 KB Output is correct
27 Correct 2291 ms 188344 KB Output is correct
28 Correct 1132 ms 190448 KB Output is correct
29 Correct 365 ms 93416 KB Output is correct
30 Correct 412 ms 99060 KB Output is correct
31 Correct 2784 ms 191144 KB Output is correct
32 Correct 2528 ms 190064 KB Output is correct
33 Correct 2408 ms 190036 KB Output is correct
34 Correct 563 ms 109168 KB Output is correct
35 Correct 1282 ms 190192 KB Output is correct
36 Correct 458 ms 109076 KB Output is correct
37 Correct 2573 ms 190036 KB Output is correct
38 Correct 2618 ms 190100 KB Output is correct
39 Correct 2703 ms 189292 KB Output is correct
40 Correct 1055 ms 189936 KB Output is correct
41 Correct 368 ms 92820 KB Output is correct
42 Correct 412 ms 98992 KB Output is correct
43 Correct 2711 ms 198468 KB Output is correct
44 Correct 2635 ms 201572 KB Output is correct
45 Correct 2551 ms 201580 KB Output is correct
46 Correct 580 ms 111388 KB Output is correct
47 Correct 1362 ms 200204 KB Output is correct
48 Correct 433 ms 108912 KB Output is correct
49 Correct 2727 ms 201580 KB Output is correct
50 Correct 2576 ms 201440 KB Output is correct
51 Correct 2772 ms 201244 KB Output is correct
52 Correct 1147 ms 199836 KB Output is correct
53 Correct 377 ms 94504 KB Output is correct