Submission #1110794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110794		vjudge1	Examination (JOI19_examination)	C++17	0 / 100	3054 ms	37192 KiB

examination

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define forn(i,a,b) for(int i = a ; i < b; i++)
#define ALL(x) x.begin(),x.end()
#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int) x.size()

struct Student{
	ll M,I; 
};

bool operator <(const Student &a, const Student &b){
	if(a.M<b.M) return true;
	if(a.M>b.M) return false;
	return (a.I<b.I);
}

struct BIT{
	ll n; 
	vector<ll> ft;
	BIT(ll n):n(n),ft(n+5,0){}
	void upd(ll x,ll y){
		while(x<=n){
			ft[x]+=y;
			x+=(x&-x);
		}
	}
	ll query(ll x){
		ll res = 0;
		while(x>=1){
			res+=ft[x];
			x-=(x&-x);
		}
		return res;
	}
};

int main(){
	ll n,q; cin>>n>>q;
	vector<pair<ll,Student>> student(n); for(auto &i:student) cin>>i.snd.M>>i.snd.I, i.fst=(i.snd.M+i.snd.I);
	vector<Student> studentS(n); forn(i,0,n) studentS[i]=student[i].snd;
	sort(ALL(student));
	vector< pair<pair<ll,ll>,pair<ll,ll> >> query(q);
	vector< pair<pair<ll,ll>,pair<ll,ll> >> queryS(q);
	sort(ALL(studentS));
	ll aux = 0;

	for(auto &i:query) cin>>i.snd.fst>>i.snd.snd>>i.fst.fst, i.fst.fst*=-1,i.fst.snd=aux, aux++;
	sort(ALL(query));
	//ll ind;
	//for(auto &i:query) ind = i.fst.snd, queryS[ind].fst.fst=i.snd.fst*-1, queryS[ind].fst.snd=i.snd.snd, queryS[ind].snd.fst = i.fst.fst , queryS[ind].snd.snd = i.fst.snd;
	forn(i,0,q){
		queryS[i].fst.fst=query[i].snd.fst*-1;
		queryS[i].fst.snd=query[i].snd.snd;
		queryS[i].snd.fst=query[i].fst.fst*-1;
		queryS[i].snd.snd=query[i].fst.snd;
	}
	
	sort(ALL(queryS));

	BIT inf(1000000);
	BIT mat(1000000);

	vector<ll> res(q);
	
	for(auto i:query){
		if(i.fst.fst*-1<i.snd.fst+i.snd.snd) continue;
		while(!student.empty()&&student[SZ(student)-1].fst>=i.fst.fst*-1){
			mat.upd(student[SZ(student)-1].snd.M,1);
			inf.upd(student[SZ(student)-1].snd.I,1);
			/*cout<<"Se agrego a "<<student[SZ(student)-1].snd.M<<" en matematica\n";
			cout<<"Se agrego a "<<student[SZ(student)-1].snd.I<<" en informatica\n";
			cout<<"Verificando matematica: "<<mat.query(student[SZ(student)-1].snd.M)-mat.query(student[SZ(student)-1].snd.M-1)<<'\n';
			cout<<"Verificando matematica: "<<inf.query(student[SZ(student)-1].snd.I)-inf.query(student[SZ(student)-1].snd.I-1)<<'\n';*/
			
			student.pop_back();	
		}
		ll mate = mat.query(1000000)-mat.query(i.snd.fst-1);
		ll info = inf.query(1000000)-inf.query(i.snd.snd-1);
		//cout<<mate<<" "<<info<<" "<<(n-SZ(student))<<'\n';
		res[i.fst.snd]=mate+info-(n-SZ(student));
	}

	BIT lbit(1000000);
	for(auto i:queryS){
		//cout<<i.snd.fst<<" "<<i.fst.fst*-1<<"+"<<i.fst.snd<<'\n';
		if(i.snd.fst>=i.fst.fst*-1+i.fst.snd) continue;
		/*cout<<"entro en la query "<<i.snd.snd<<'\n';
		cout<<studentS[SZ(studentS)-1].M<<'\n';*/
		while(!studentS.empty()&&studentS[SZ(studentS)-1].M>=i.fst.fst*-1){
			lbit.upd(studentS[SZ(studentS)-1].I,1);
			//cout<<"Se agrego "<<studentS[SZ(studentS)-1].I<<" a informatica.\n";
			studentS.pop_back();
		}
		//cout<<lbit.query(1000000)<<'\n';
		res[i.snd.snd]=lbit.query(1000000)-lbit.query(i.fst.snd-1);
	}
	
	for(auto i:res) cout<<i<<'\n';
	return 0;
}

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