oj.uz

Submission #219055

# Submission time Handle Problem Language Result Execution time Memory
219055 2020-04-03T14:11:57 Z kshitij_sodani Examination (JOI19_examination) C++17
100 / 100
 957 ms 128084 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
bool cmp(pair<pair<llo,llo>,pair<llo,llo>> ac,pair<pair<llo,llo>,pair<llo,llo>> cc){
	return ac.b.a<cc.b.a;
}
bool cmp2(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cd){
	return ac.a.a+ac.a.b<cd.a.a+cd.a.b;
}
bool cmp3(pair<pair<llo,llo>,llo> ac,pair<pair<llo,llo>,llo> cc){
	return ac.a.a<cc.a.a;
}
vector<llo> tree[400001];
vector<pair<llo,llo>> ss[400001];
vector<llo> indd[400001];
pair<llo,llo> bb[100001];
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
//	freopen((name+".out").c_str(),"w",stdout);
}
void u(llo no,llo i,llo j){
	while(i<tree[no].size()){
		tree[no][i]+=j;
		i+=(i&-i);
	}
}
llo st(llo no,llo i){
	llo tot=0;
	while(i>0){
		tot+=tree[no][i];
		i-=(i&-i);
	}
	return tot;
}
void build(llo no,llo l,llo r){
	for(llo i=l;i<=r+2;i++){
		tree[no].pb(0);
		indd[no].pb(0);
	}
	if(r>l){
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		llo ind=0;
		llo ind2=0;
		llo ind3=0;
		while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
			if(ss[no*2+1][ind].a<ss[no*2+2][ind2].a){
				ss[no].pb(ss[no*2+1][ind]);
				indd[no][ss[no*2+1][ind].b-l]=ind3;
				ind+=1;
				ind3+=1;
			}
			else{
				ss[no].pb(ss[no*2+2][ind2]);
				indd[no][ss[no*2+2][ind2].b-l]=ind3;
				ind2+=1;
				ind3+=1;
			}
		}
		while(ind<ss[no*2+1].size() ){
			ss[no].pb(ss[no*2+1][ind]);
			indd[no][ss[no*2+1][ind].b-l]=ind3;
			ind+=1;
			ind3+=1;
		}
		while(ind2<ss[no*2+2].size()){
			ss[no].pb(ss[no*2+2][ind2]);
			indd[no][ss[no*2+2][ind2].b-l]=ind3;
			ind2+=1;
			ind3+=1;
		}
	}
	else{
		ss[no].pb({bb[l].b,l});
	}
}
void update(llo no,llo l,llo r,llo ind){
	if(ind<l or ind>r){
		return;
	}
	u(no,indd[no][ind-l]+1,1);
	if(r>l){
		llo mid=(l+r)/2;
		update(no*2+1,l,mid,ind);
		update(no*2+2,mid+1,r,ind);
	}
}
llo kk;
llo cp;
llo query(llo no,llo l,llo r){
	if(bb[r].a<kk){
		return 0;
	}

	if(bb[l].a>=kk){
		if(ss[no][r-l].a<cp){
			return 0;
		}
		llo low=0;
		llo high=r-l;
		while(low<high-1){
			llo mid=(low+high)/2;
			if(ss[no][mid].a>=cp){
				high=mid;
			}
			else{
				low=mid+1;
			}
		}
		llo dd=high;
		if(ss[no][low].a>=cp){
			dd=low;
		}
		llo xx=st(no,r-l+1);
		if(dd>0){
			xx-=st(no,dd);
		}
		return xx;
	}
	else{
		llo mid=(l+r)/2;
		return query(no*2+1,l,mid)+query(no*2+2,mid+1,r);
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	llo n,q;
	//setIO("11");
	cin>>n>>q;
	vector<pair<pair<llo,llo>,llo>> aa;
	llo mm,nn;
	for(llo i=0;i<n;i++){
		cin>>mm>>nn;
		aa.pb({{mm,nn},0});
	}
	sort(aa.begin(),aa.end(),cmp3);
	for(llo i=0;i<n;i++){
		aa[i].b=i;
	}
	for(llo i=0;i<n;i++){
		bb[i]=aa[i].a;
	}

	sort(aa.begin(),aa.end(),cmp2);

	

	llo pp,bc,cd;
	vector<pair<pair<llo,llo>,pair<llo,llo>>> qq;
	for(llo i=0;i<q;i++){
		cin>>pp>>bc>>cd;
		qq.pb({{pp,bc},{cd,i}});
	}
	sort(qq.begin(),qq.end(),cmp);
	llo pos=n-1;
	llo ans[q];
	build(0,0,n-1);
//	cout<<33<<endl;

	for(llo ii=q-1;ii>=0;ii--){
		llo ba=qq[ii].b.a;
     	while(pos>=0){
			if(aa[pos].a.a+aa[pos].a.b>=ba){
				update(0,0,n-1,aa[pos].b);
			//	cout<<aa[pos].b<<" "<<ii<<endl;
				pos-=1;
			}
			else{
				break;
			}
		}
		kk=qq[ii].a.a;
		cp=qq[ii].a.b;
		llo ans4=query(0,0,n-1);
		ans[qq[ii].b.b]=ans4;
	}
	for(llo i=0;i<q;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

Compilation message

examination.cpp: In function 'void u(llo, llo, llo)':
examination.cpp:29:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<tree[no].size()){
        ~^~~~~~~~~~~~~~~~
examination.cpp: In function 'void build(llo, llo, llo)':
examination.cpp:54:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:54:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() and ind2<ss[no*2+2].size()){
                                   ~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind<ss[no*2+1].size() ){
         ~~~^~~~~~~~~~~~~~~~~~
examination.cpp:74:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ind2<ss[no*2+2].size()){
         ~~~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'void setIO(std::__cxx11::string)':
examination.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((name+".in").c_str(),"r",stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28672 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 22 ms 28544 KB Output is correct
6 Correct 22 ms 28544 KB Output is correct
7 Correct 38 ms 30976 KB Output is correct
8 Correct 35 ms 30848 KB Output is correct
9 Correct 36 ms 30976 KB Output is correct
10 Correct 35 ms 30848 KB Output is correct
11 Correct 34 ms 30840 KB Output is correct
12 Correct 37 ms 30940 KB Output is correct
13 Correct 33 ms 31096 KB Output is correct
14 Correct 33 ms 31096 KB Output is correct
15 Correct 33 ms 30976 KB Output is correct
16 Correct 31 ms 30972 KB Output is correct
17 Correct 35 ms 31048 KB Output is correct
18 Correct 29 ms 30976 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 123356 KB Output is correct
2 Correct 869 ms 125788 KB Output is correct
3 Correct 872 ms 125788 KB Output is correct
4 Correct 652 ms 125012 KB Output is correct
5 Correct 713 ms 125016 KB Output is correct
6 Correct 577 ms 124252 KB Output is correct
7 Correct 784 ms 125652 KB Output is correct
8 Correct 791 ms 125636 KB Output is correct
9 Correct 742 ms 125532 KB Output is correct
10 Correct 645 ms 124892 KB Output is correct
11 Correct 520 ms 124756 KB Output is correct
12 Correct 409 ms 123856 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 123356 KB Output is correct
2 Correct 869 ms 125788 KB Output is correct
3 Correct 872 ms 125788 KB Output is correct
4 Correct 652 ms 125012 KB Output is correct
5 Correct 713 ms 125016 KB Output is correct
6 Correct 577 ms 124252 KB Output is correct
7 Correct 784 ms 125652 KB Output is correct
8 Correct 791 ms 125636 KB Output is correct
9 Correct 742 ms 125532 KB Output is correct
10 Correct 645 ms 124892 KB Output is correct
11 Correct 520 ms 124756 KB Output is correct
12 Correct 409 ms 123856 KB Output is correct
13 Correct 934 ms 126156 KB Output is correct
14 Correct 906 ms 126164 KB Output is correct
15 Correct 853 ms 125780 KB Output is correct
16 Correct 666 ms 125396 KB Output is correct
17 Correct 796 ms 125404 KB Output is correct
18 Correct 593 ms 124244 KB Output is correct
19 Correct 922 ms 126172 KB Output is correct
20 Correct 926 ms 126232 KB Output is correct
21 Correct 859 ms 126172 KB Output is correct
22 Correct 619 ms 124840 KB Output is correct
23 Correct 505 ms 124756 KB Output is correct
24 Correct 410 ms 123796 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28672 KB Output is correct
2 Correct 22 ms 28544 KB Output is correct
3 Correct 22 ms 28544 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 22 ms 28544 KB Output is correct
6 Correct 22 ms 28544 KB Output is correct
7 Correct 38 ms 30976 KB Output is correct
8 Correct 35 ms 30848 KB Output is correct
9 Correct 36 ms 30976 KB Output is correct
10 Correct 35 ms 30848 KB Output is correct
11 Correct 34 ms 30840 KB Output is correct
12 Correct 37 ms 30940 KB Output is correct
13 Correct 33 ms 31096 KB Output is correct
14 Correct 33 ms 31096 KB Output is correct
15 Correct 33 ms 30976 KB Output is correct
16 Correct 31 ms 30972 KB Output is correct
17 Correct 35 ms 31048 KB Output is correct
18 Correct 29 ms 30976 KB Output is correct
19 Correct 866 ms 123356 KB Output is correct
20 Correct 869 ms 125788 KB Output is correct
21 Correct 872 ms 125788 KB Output is correct
22 Correct 652 ms 125012 KB Output is correct
23 Correct 713 ms 125016 KB Output is correct
24 Correct 577 ms 124252 KB Output is correct
25 Correct 784 ms 125652 KB Output is correct
26 Correct 791 ms 125636 KB Output is correct
27 Correct 742 ms 125532 KB Output is correct
28 Correct 645 ms 124892 KB Output is correct
29 Correct 520 ms 124756 KB Output is correct
30 Correct 409 ms 123856 KB Output is correct
31 Correct 934 ms 126156 KB Output is correct
32 Correct 906 ms 126164 KB Output is correct
33 Correct 853 ms 125780 KB Output is correct
34 Correct 666 ms 125396 KB Output is correct
35 Correct 796 ms 125404 KB Output is correct
36 Correct 593 ms 124244 KB Output is correct
37 Correct 922 ms 126172 KB Output is correct
38 Correct 926 ms 126232 KB Output is correct
39 Correct 859 ms 126172 KB Output is correct
40 Correct 619 ms 124840 KB Output is correct
41 Correct 505 ms 124756 KB Output is correct
42 Correct 410 ms 123796 KB Output is correct
43 Correct 946 ms 128084 KB Output is correct
44 Correct 957 ms 128084 KB Output is correct
45 Correct 935 ms 128084 KB Output is correct
46 Correct 678 ms 126548 KB Output is correct
47 Correct 810 ms 126548 KB Output is correct
48 Correct 598 ms 124124 KB Output is correct
49 Correct 843 ms 127956 KB Output is correct
50 Correct 861 ms 127988 KB Output is correct
51 Correct 792 ms 127836 KB Output is correct
52 Correct 677 ms 126300 KB Output is correct
53 Correct 530 ms 125652 KB Output is correct