Submission #103354

#	Time	Username	Problem	Language	Result	Execution time	Memory
103354		tincamatei	Examination (JOI19_examination)	C++14	100 / 100	2163 ms	56512 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;

typedef struct Node {
	Node *l, *r;
	int key, prio, size;

	Node(int k) {
		key = k;
		prio = rand();
		size = 1;
		l = r = NULL;
	}

	void refresh() {
		size = 1;
		if(l != NULL) size += l->size;
		if(r != NULL) size += r->size;
	}
} *Treap;

Treap join(Treap a, Treap b) {
	if(a == NULL) return b;
	if(b == NULL) return a;

	if(a->prio < b->prio) {
		a->r = join(a->r, b);
		a->refresh();
		return a;
	} else {
		b->l = join(a, b->l);
		b->refresh();
		return b;
	}
}

void split(Treap t, int val, Treap &l, Treap &r) {
	l = r = NULL;
	if(t == NULL) return;

	if(t->key < val) {
		split(t->r, val, t->r, r);
		t->refresh();
		l = t;
	} else {
		split(t->l, val, l, t->l);
		t->refresh();
		r = t;
	}
}

Treap add(Treap t, int x) {
	Treap l, r;
	split(t, x, l, r);
	return join(join(l, new Node(x)), r);
}

struct Student {
	int t, s, sum;
} 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.sum > b.sum;
}

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

Treap aib[1+MAX_AIB];

void init2dstructure() {
	for(int i = 0; i <= MAX_AIB; ++i)
		aib[i] = NULL;
}

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

void updatePoint(int x, int y) {
	while(x <= MAX_AIB) {
		aib[x] = add(aib[x], y);
		x += lsb(x);
	}
}

int queryRectangle(int a, int b) {
	int rez = 0;

	while(a > 0) {
		Treap l, r;
		split(aib[a], b + 1, l, r);
		
		if(l != NULL)
			rez = rez + l->size;
		
		aib[a] = join(l, r);
		a -= lsb(a);
	}
	return rez;
}

bool cmp(int *a, int *b) {
	return *a < *b;
}

int *coordA[MAX_AIB], *coordB[MAX_AIB];

void normalize(int n, int **v) {
	sort(v, v + n, cmp);
	int last = *v[0], j = MAX_AIB;
	for(int i = 0; i < n; ++i)
		if(*v[i] == last)
			*v[i] = j;
		else {
			last = *v[i];
			*v[i] = --j;
		}
}

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;
	int top = 0;
	fscanf(fin, "%d%d", &n, &q);
	for(int i = 0; i < n; ++i) {
		fscanf(fin, "%d%d", &v[i].t, &v[i].s);
		v[i].sum = v[i].t + v[i].s;
		coordA[top] = &v[i].t;
		coordB[top++] = &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];
		coordA[top] = &query[i].a;
		coordB[top++] = &query[i].b;
	}
	
	normalize(top, coordA);
	normalize(top, coordB);

	sort(v, v + n, cmp1);
	sort(query, query + q, cmp2);

	init2dstructure();

	int lastup = 0;
	for(int i = 0; i < q; ++i) {
		while(lastup < n && v[lastup].sum >= 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:145: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:147: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:153: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: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57