Submission #403808

#	Time	Username	Problem	Language	Result	Execution time	Memory
403808		pure_mem	Examination (JOI19_examination)	C++14	100 / 100	1189 ms	282652 KiB

examination

#include <bits/stdc++.h> 
 
#define X first
#define Y second
#define MP make_pair
#define ll long long
 
using namespace std;
 
const int N = 1e5 + 12;
const ll INF = 1e18;

struct node{
	int val = 0;
	node* to[2] = {nullptr, nullptr};
	node* getp(int v){
		if(!to[v])
			to[v] = new node();
		return to[v];
	}		
	void upd(int tl, int tr, int pos){
		val += 1;
		if(tl == tr)
			return;
		int tm = (tl + tr) / 2;
		if(pos <= tm)
			getp(0)->upd(tl, tm, pos);
		else
			getp(1)->upd(tm + 1, tr, pos);
	}
	int get(int tl, int tr, int l, int r){
		if(tl > r || l > tr)
			return 0;
		if(tl >= l && tr <= r)
			return val;
		int tm = (tl + tr) / 2;
		return (to[0] ? to[0]->get(tl, tm, l, r): 0) + (to[1] ? to[1]->get(tm + 1, tr, l, r): 0);
	}
};
node fw[N];

vector< int > sqA, sqB, sqC;
vector< pair< int, int > > todo[N];
vector< pair< pair< int, int >, int > > query[N];

int n, q, answer[N];
pair< int, int > p[N];

void add(int x, int y){
	for(;x <= sqA.size();x |= x + 1)
		fw[x].upd(1, sqB.size(), y);//, cerr << x << " " << y << "s\n";
}
int get(int x, int y){
	int r = 0;
	for(;x >= 0;x = (x & (x + 1)) - 1)
		r += fw[x].get(1, sqB.size(), 1, y);
	return r;
}

int main () {
	ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n >> q;
	for(int i = 1;i <= n;i++){
		cin >> p[i].X >> p[i].Y;
		sqA.push_back(p[i].X), sqB.push_back(p[i].Y), sqC.push_back(p[i].X + p[i].Y);
	}
	sort(sqA.begin(), sqA.end()), sqA.erase(unique(sqA.begin(), sqA.end()), sqA.end());
	sort(sqB.begin(), sqB.end()), sqB.erase(unique(sqB.begin(), sqB.end()), sqB.end());
	sort(sqC.begin(), sqC.end()), sqC.erase(unique(sqC.begin(), sqC.end()), sqC.end());
	for(int i = 1;i <= n;i++){
		int it1 = lower_bound(sqA.begin(), sqA.end(), p[i].X) - sqA.begin();
		int it2 = lower_bound(sqB.begin(), sqB.end(), p[i].Y) - sqB.begin();		
		int it3 = lower_bound(sqC.begin(), sqC.end(), p[i].X + p[i].Y) - sqC.begin();
		todo[it3].push_back(MP(sqA.size() - it1, sqB.size() - it2));
	}
	for(int i = 1, x, y, z;i <= q;i++){
		cin >> x >> y >> z;
		int it1 = lower_bound(sqA.begin(), sqA.end(), x) - sqA.begin();
		int it2 = lower_bound(sqB.begin(), sqB.end(), y) - sqB.begin();		
		int it3 = lower_bound(sqC.begin(), sqC.end(), z) - sqC.begin();
		query[it3].push_back(MP(MP(sqA.size() - it1, sqB.size() - it2), i));
	}
	for(int i = (int)sqC.size() - 1;i >= 0;i--){
		for(pair<int, int> tmp: todo[i]){
		//	cerr << tmp.X << " " << tmp.Y << " " << i << "\n";
			add(tmp.X, tmp.Y);
		}	
		for(pair< pair<int, int>, int > tmp: query[i]){
		//	cerr << "was " << tmp.X.X << " " << tmp.X.Y << " " << i << "\n";
			answer[tmp.Y] = get(tmp.X.X, tmp.X.Y);
		}
	}
	for(int i = 1;i <= q;i++)
		cout << answer[i] << "\n";
}                

Compilation message (stderr)

examination.cpp: In function 'void add(int, int)':
examination.cpp:50:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(;x <= sqA.size();x |= x + 1)
      |       ~~^~~~~~~~~~~~~

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