Submission #331376

#	Time	Username	Problem	Language	Result	Execution time	Memory
331376		GioChkhaidze	Examination (JOI19_examination)	C++14	100 / 100	1521 ms	134120 KiB

examination

#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define pb push_back

using namespace std;

const int N=1e5+5;

int n,q,sz,res;
map < int , int > f;
vector < int > Qa,Qp,s,G[2*N],vrs[8*N],Fe[8*N];
int A[N],B[N],S[N],X[N],Y[N],Z[N],ans[N],all[8*N];

void Build(Tree) {
	for (int i=l; i<=r; i++)
		for (int j=0; j<G[i].size(); j++) 
			vrs[h].pb(G[i][j]);
	
	sort(vrs[h].begin(),vrs[h].end());

	if (l==r) return ; 
	Build(Left);
	Build(Right);
}

void Up(int h,int idx) {
	all[h]++;
	while (idx<=vrs[h].size()) {
		Fe[h][idx]++;
		idx+=(idx & -idx);
	}
}

int Ge(int h,int idx) {
	res=0;
	while (idx>0) {
		res+=Fe[h][idx];
		idx-=(idx & -idx);
	}
	return res;
}

inline int V(int h,int x) {
	return (lower_bound(vrs[h].begin(),vrs[h].end(),x)-vrs[h].begin()+1);
}

void Upd(Tree,int id,int vl) {
	if (id<l || r<id) return ;
	Up(h,V(h,vl));
	if (l==id && id==r) return ;	
	Upd(Left,id,vl);
	Upd(Right,id,vl);
}

int Get(Tree,int L,int R,int vl) {
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return all[h]-Ge(h,V(h,vl)-1);
	return Get(Left,L,R,vl)+Get(Right,L,R,vl);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	cin>>n>>q;
	for (int i=1; i<=n; i++) {
		cin>>A[i]>>B[i];
		S[i]=A[i]+B[i];
		s.pb(A[i]);
		Qp.pb(i);
	}
	
	for (int i=1; i<=q; i++) {
		cin>>X[i]>>Y[i]>>Z[i];
		s.pb(X[i]);
		Qa.pb(i);
	}
	 
	sort(s.begin(),s.end());
	for (int i=0; i<s.size(); i++) {
		if (!i || s[i]!=s[i-1]) f[s[i]]=++sz;
	}
	
	sort(Qa.begin(),Qa.end(),[](int a,int b) { return Z[a]<Z[b]; } );
	sort(Qp.begin(),Qp.end(),[](int a,int b) { return S[a]<S[b]; });
	
	for (int i=1; i<=n; i++) 
		A[i]=f[A[i]],G[A[i]].pb(B[i]);
	
	for (int i=1; i<=q; i++) 
		X[i]=f[X[i]],G[X[i]].pb(Y[i]);
	
	Build(1,1,sz);
	
	for (int i=1; i<=4*sz; i++) {
		Fe[i].resize(vrs[i].size()+1);
	}
	
	int j=Qp.size()-1;
	for (int i=Qa.size()-1; i>=0; i--) {
		int id=Qa[i];
		
		while (0<=j && Z[id]<=S[Qp[j]]) {
			Upd(1,1,sz,A[Qp[j]],B[Qp[j]]);
			--j;
		}

		ans[id]=Get(1,1,sz,X[id],sz,Y[id]);
	}
	
	for (int i=1; i<=q; i++)
		cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'void Build(int, int, int)':
examination.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int j=0; j<G[i].size(); j++)
      |                 ~^~~~~~~~~~~~
examination.cpp: In function 'void Up(int, int)':
examination.cpp:31:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  while (idx<=vrs[h].size()) {
      |         ~~~^~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:64:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   64 | main () {
      |       ^
examination.cpp: In function 'int main()':
examination.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i=0; i<s.size(); i++) {
      |                ~^~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57