Submission #172908

#	Time	Username	Problem	Language	Result	Execution time	Memory
172908		ZwariowanyMarcin	Examination (JOI19_examination)	C++14	100 / 100	1569 ms	209496 KiB

examination

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 1e5 + 111;
const int pod = (1 << 17);

int n, q;
pair<int, int> t[nax];

struct gao {
	int x, y, z, id;
	bool operator <(gao a) const {
		return z < a.z;
	}
};

vector <gao> qu;

vector <int> val[2];

int daj(int x, int k) {
	return (int) (lower_bound(val[k].begin(), val[k].end(), x) - val[k].begin()) + 1;
}

struct nod {
	nod *l, *r;
	int sum;
};

nod T[30000000];
nod *wsk = T;

nod* aloc() {
	nod *r = wsk++;
	r->sum = 0;
	return r;
}

#define mak(x) x ? x : x = aloc()

void add(int x, nod *u, int l = 0, int r = pod - 1) {
	if(l == r) {
		u->sum++;
		return;
	}
	int m = (l + r) / 2;
	if(x <= m)	
		add(x, mak(u->l), l, m);
	else
		add(x, mak(u->r), m + 1, r);
	u->sum = (u->l ? u->l->sum : 0) + (u->r ? u->r->sum : 0);
}

int query(int x, int y, nod *u, int l = 0, int r = pod - 1) {
	if(!u) return 0;
	if(x <= l && r <= y) 
		return u->sum;
	int m = (l + r) / 2;
	int res = 0;
	if(x <= m)
		res += query(x, y, u->l, l, m);
	if(m < y)
		res += query(x, y, u->r, m + 1, r);
	return res;
}

nod *root[nax];
	
void addfen(int x, int y) {
	for(int i = x; i < nax; i += i & -i) 
		add(y, root[i]);
}

int queryfen(int x, int y) {
	int res = 0;
	for(int i = x; 0 < i; i -= i & -i)
		res += query(y, pod - 1, root[i]);
	return res;
}

int qq(int x, int y) {
	return queryfen(nax - 1, y) - queryfen(x - 1, y);
}	

int ans[nax];
			
int main() {
	scanf("%d %d", &n, &q);
	for(int i = 1; i <= n; ++i) {
		scanf("%d %d", &t[i].fi, &t[i].se);
		val[0].pb(t[i].fi);
		val[1].pb(t[i].se);
	}
	
	sort(t + 1, t + n + 1, [](pair<int,int> a, pair<int,int> b) {
		return a.fi + a.se < b.fi + b.se;
	});
	
	for(int i = 1; i <= q; ++i) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		qu.pb({x, y, z, i});
	}
	
	for(int i = 0; i < 2; ++i) {
		sort(val[i].begin(), val[i].end());
		val[i].erase(unique(val[i].begin(), val[i].end()), val[i].end());
	}
	
	sort(qu.begin(), qu.end());
		
	for(int i = 1; i < nax; ++i)
		root[i] = aloc();
		
	int wsk = n;
	
	for(int i = q - 1; 0 <= i; --i) {
		while(wsk >= 1 && qu[i].z <= t[wsk].fi + t[wsk].se) {
			addfen(daj(t[wsk].fi, 0), daj(t[wsk].se, 1));
			wsk--;
		}
		ans[qu[i].id] = qq(daj(qu[i].x, 0), daj(qu[i].y, 1));
	}
	
	for(int i = 1; i <= q; ++i)
		printf("%d\n", ans[i]);
	

	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &t[i].fi, &t[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &x, &y, &z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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