Submission #103352

#	Time	Username	Problem	Language	Result	Execution time	Memory
103352		tincamatei	Examination (JOI19_examination)	C++14	2 / 100	3047 ms	222892 KiB

examination

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100000;
const int MAX_Q = 100000;
const int MAX_AIB = MAX_N + MAX_Q;
const int INF = 1000000001;

struct Student {
	int t, s;
} v[MAX_N];

struct Query {
	int a, b, c;
	int *rez;
} query[MAX_Q];

int rez[MAX_Q];

bool cmp1(Student a, Student b) {
	return a.t + a.s > b.t + b.s;
}

bool cmp2(Query a, Query b) {
	return a.c > b.c;
}

unordered_map<int, unordered_map<int, int> > aib;

static inline int lsb(int x) {
	return x & (-x);
}

void updateAib(int i, int j) {
	while(i <= INF) {
		int jc = j;
		while(jc <= INF) {
			aib[i][jc]++;
			jc += lsb(jc);
		}
		i += lsb(i);
	}
}

int queryAib(int i, int j) {
	int rez = 0;
	while(i > 0) {
		int jc = j;
		while(jc > 0) {
			rez += aib[i][jc];
			jc -= lsb(jc);
		}
		i -= lsb(i);
	}
	return rez;
}

void updatePoint(int a, int b) {
	updateAib(INF - a, INF - b);
}

int queryRectangle(int a, int b) {
	return queryAib(INF - a, INF - b);
}

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, q;
	fscanf(fin, "%d%d", &n, &q);
	for(int i = 0; i < n; ++i)
		fscanf(fin, "%d%d", &v[i].t, &v[i].s);
	for(int i = 0; i < q; ++i) {
		fscanf(fin, "%d%d%d", &query[i].a, &query[i].b, &query[i].c);
		query[i].rez = &rez[i];
	}

	sort(v, v + n, cmp1);
	sort(query, query + q, cmp2);
	
	int lastup = 0;
	for(int i = 0; i < q; ++i) {
		while(lastup < n && v[lastup].t + v[lastup].s >= query[i].c) {
			updatePoint(v[lastup].t, v[lastup].s);
			++lastup;
		}

		*query[i].rez = queryRectangle(query[i].a, query[i].b);
	}
	
	for(int i = 0; i < q; ++i)
		fprintf(fout, "%d\n", rez[i]);

	fclose(fin);
	fclose(fout);
	return 0;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:77:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d", &n, &q);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:79:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &v[i].t, &v[i].s);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:81:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d%d", &query[i].a, &query[i].b, &query[i].c);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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