Submission #157199

#	Time	Username	Problem	Language	Result	Execution time	Memory
157199		manh9203	Examination (JOI19_examination)	C++17	100 / 100	2657 ms	257876 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#pragma GCC optimize("O3")
const int N = 3e5 + 5;
long long n,w,h,q,x[N],y[N],z[N],ans[N],cnt;
pair<long long,long long> stu[N];
pair<pair<int,int>,long long> com[N];
map<long long,int> idx,idy;
vector<long long> dmx,dmy,pos[N],node1[4*N];
vector<int> fen[4*N],point[N],query[N];
vector<pair<long long,int> > node[4*N];
//compress
void build1(int id,int l,int r,int i,int vt){
	if(l>i || r<i){
		return;
	}
	if(l == r){
		node[id].push_back({com[vt].se, vt});
		node1[id].push_back(com[vt].se);
		return;		
	}
	int mid = (l + r) >> 1;
	build1(id<<1, l, mid, i, vt);
	build1(id<<1|1, mid+1, r, i, vt);
	node[id].push_back({com[vt].se, vt});
	node1[id].push_back(com[vt].se);
}

void build(int id,int l,int r){
	if(l == r){
		sort(node[id].begin(), node[id].end());
		sort(node1[id].begin(), node1[id].end());
		for(int i = 0; i < node[id].size(); i++){
			pos[node[id][i].se].push_back(i + 1);
		}
		fen[id].assign(node[id].size() + 5, 0);
		return;
	}
	int mid = (l + r) >> 1;
	build(id<<1, l, mid);
	build(id<<1|1, mid+1, r);
	sort(node[id].begin(), node[id].end());
	sort(node1[id].begin(), node1[id].end());
	for(int i = 0; i < node[id].size(); i++){
		pos[node[id][i].se].push_back(i + 1);
	}
	fen[id].assign(node[id].size() + 5, 0);
}

//upd BIT
void upd(int id,int val,int index){
	for(int i = id; i <= node[index].size(); i += (i&-i)){
		fen[index][i] += val;
	}
}
int get_sum(int id,int index){
	int sum = 0;
	for(int i = id; i >= 1; i -= (i&-i)){
		sum += fen[index][i];
	}
	return sum;
}

//sweep update
void update(int id,int l,int r,int i,int vt){
	if(l>i || r<i){
		return;
	}
	if(l == r){
		cnt++;
		upd(pos[vt][cnt], 1, id);
		return;
	}
	int mid = (l + r) >> 1;
	update(id<<1, l, mid, i, vt);
	update(id<<1|1, mid+1, r, i, vt);
	cnt++;
	upd(pos[vt][cnt], 1, id);
}

//ans query
int get(int id,int l,int r,int i,int j,long long val){
	if(l>j || r<i || i>j){
		return 0;
	}
	if(l>=i && r<=j){
		if(node1[id].size() == 0 || node1[id][node1[id].size()-1] < val){
			return 0;
		}else{
			int dm1 = lower_bound(node1[id].begin(), node1[id].end(), val) - node1[id].begin();
			return get_sum(node1[id].size(), id) - get_sum(dm1, id);
		}
	}
	int mid = (l + r) >> 1;
	return get(id<<1, l, mid, i, j, val) + get(id<<1|1, mid+1, r, i, j, val);
}

//main
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> stu[i].fi >> stu[i].se;
		if(idx[stu[i].fi] == 0){
			idx[stu[i].fi] = 1;
			dmx.push_back(stu[i].fi);
		}
		if(idy[stu[i].se] == 0){
			idy[stu[i].se] = 1;
			dmy.push_back(stu[i].se);
		}
	}
	for(int i=1;i<=q;i++){
		cin >> x[i] >> y[i] >> z[i];
		if(idx[x[i]] == 0){
			idx[x[i]] = 1;
			dmx.push_back(x[i]);
		}
		if(idy[y[i]] == 0){
			idy[y[i]] = 1;
			dmy.push_back(y[i]);
		}
	}
	sort(dmx.begin(), dmx.end());
	sort(dmy.begin(), dmy.end());
	w = dmx.size(); h = dmy.size();
	for(int i=0;i<dmx.size();i++){
		idx[dmx[i]] = i+1;
	}
	for(int i=0;i<dmy.size();i++){
		idy[dmy[i]] = i+1;
	}
	for(int i=1;i<=n;i++){
		com[i].fi.fi = idx[stu[i].fi];
		com[i].fi.se = idy[stu[i].se];
		com[i].se = stu[i].fi + stu[i].se;
	}
	for(int i=1;i<=q;i++){
		x[i] = idx[x[i]];
		y[i] = idy[y[i]];
		query[x[i]].push_back(i);
	}
	sort(com+1, com+1+n);
	for(int i=1;i<=n;i++){
		build1(1, 1, h, com[i].fi.se, i);
		point[com[i].fi.fi].push_back(i);
	}
	build(1, 1, h);
	for(int i = w; i >= 1; i--){
		for(int j: point[i]){
			cnt = -1;
			update(1, 1, h, com[j].fi.se, j);
		}
		for(int j: query[i]){
			ans[j] = get(1, 1, h, y[j], h, z[j]);
		}
	}
	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:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < node[id].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~
examination.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < node[id].size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = id; i <= node[index].size(); i += (i&-i)){
                  ~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:129:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmx.size();i++){
              ~^~~~~~~~~~~
examination.cpp:132:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmy.size();i++){
              ~^~~~~~~~~~~

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