oj.uz

Submission #91204

# Submission time Handle Problem Language Result Execution time Memory
91204 2018-12-26T14:21:14 Z tincamatei New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 445384 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 300000;

struct Store {
	int x, t, a, b;
};

struct Event {
	int time, x, t, id;
	bool scoate;
};

struct Query {
	int l, y;
	int *rez;
};

bool cmp1(Event a, Event b) { return a.time < b.time; }
bool cmp2(int *a, int *b) { return *a < *b; }
bool cmp3(Query a, Query b) { return a.y < b.y; }

Store v[MAX_N];
int auxx[2*MAX_N];
Event event[2*MAX_N];
Query query[MAX_N];
int rez[MAX_N];
bool activeStore[MAX_N];

set<pair<int, int> > typestore[1+MAX_N];

vector<pair<int, int> > transf;

void normalize(int n) {
	vector<int*> vp;
	for(int i = 0; i < n; ++i)
		vp.push_back(&auxx[i]);
	
	sort(vp.begin(), vp.end(), cmp2);
	int lastV = -1, j = 0;
	
	for(auto it: vp) {
		if(*it == lastV)
			*it = j;
		else {
			lastV = *it;
			transf.push_back(make_pair(*it, ++j));
			*it = j;
		}
	}
}

priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> bigboi[1+8*MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int>>, std::less<pair<int, int>>> smallboi[1+8*MAX_N];

void updateAint(int pozl, int pozr, pair<int, int> val, int l, int r, int nod = 1) {
	if(r < l || r < pozl || pozr < l || pozr < pozl) return;
	
	if(pozl <= l && r <= pozr) {
		bigboi[nod].push(val);
		smallboi[nod].push(val);
	} else if(l < r) {
		int mid = (l + r) / 2;
		updateAint(pozl, pozr, val, l, mid, 2 * nod);
		updateAint(pozl, pozr, val, mid + 1, r, 2 * nod + 1);
	}
}

pair<int, int> add(pair<int, int> a, pair<int, int> b) {
	return make_pair(min(a.first, b.first), max(a.second, b.second));
}

pair<int, int> queryAint(int poz, int l, int r, int nod = 1) {
	pair<int, int> rezQ(1000000000, -1000000000);
	if(r < poz || poz < l || r < l)	return rezQ;

	while(!bigboi[nod].empty() && !activeStore[bigboi[nod].top().second])
		bigboi[nod].pop();
	while(!smallboi[nod].empty() && !activeStore[smallboi[nod].top().second])
		smallboi[nod].pop();
	
	if(!smallboi[nod].empty())
		rezQ.first = min(rezQ.first, smallboi[nod].top().first);
	if(!bigboi[nod].empty())
		rezQ.second = max(rezQ.second, bigboi[nod].top().first);

	if(l < r) {
		int mid = (l + r) / 2;
		rezQ = add(queryAint(poz, l, mid, 2 * nod),
		       add(queryAint(poz, mid + 1, r, 2 * nod + 1),
					     rezQ));
	}
	return rezQ;
}

int getId(int x) {
	int st = 0, dr = transf.size();

	while(dr - st > 1) {
		int mid = (st + dr) / 2;
		if(transf[mid].first <= x)
			st = mid;
		else
			dr = mid;
	}

	return transf[st].second;
}

void updateRange(pair<int, int> st, pair<int, int> dr) {
	pair<int, int> nullpair(-1, -1);
	if(st != nullpair && dr != nullpair) {
		int mid = (st.first + dr.first) / 2;
		updateAint(getId(st.first) + 1, getId(mid), st, 1, transf.size(), 1);
		updateAint(getId(mid) + 1, getId(dr.first) - 1, dr, 1, transf.size(), 1);
	} else if(st != nullpair) {
		updateAint(getId(st.first) + 1, transf.size(), st, 1, transf.size(), 1);
	} else if(dr != nullpair) {
		updateAint(1, getId(dr.first) - 1, dr, 1, transf.size(), 1);
	}
}

void addStore(int l, int t, int i) {
	set<pair<int, int> >::iterator it;
	pair<int, int> st, dr, val(l, i);
	it = typestore[t].lower_bound(val);
	if(it == typestore[t].end()) dr = make_pair(-1, -1);
	else                         dr = *it;
	if(it == typestore[t].begin()) st = make_pair(-1, -1);
	else {
		it--;
		st = *it;
	}
	
	updateRange(st, dr);
	
	typestore[t].insert(val);
	updateRange(st, val);
	updateRange(val, dr);

	activeStore[i] = true;
}

void eraseStore(int l, int t, int i) {
	set<pair<int, int> >::iterator it;
	pair<int, int> st, dr, val(l, i);
	
	it = typestore[t].find(val);
	
	it++;
	if(it == typestore[t].end()) dr = make_pair(-1, -1);
	else                         dr = *it;

	it--;
	if(it == typestore[t].begin()) st = make_pair(-1, -1);
	else {
		it--;
		st = *it;
	}

	updateRange(st, val);
	updateRange(val, dr);

	typestore[t].erase(val);
	updateRange(st, dr);

	activeStore[i] = false;
}

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, k, q;
	fscanf(fin, "%d%d%d", &n, &k, &q);

	for(int i = 0; i < n; ++i) {
		fscanf(fin, "%d%d%d%d", &v[i].x, &v[i].t, &v[i].a, &v[i].b);
		auxx[i] = v[i].x;
		event[2 * i]     = {v[i].a, v[i].x, v[i].t, i, false};
		event[2 * i + 1] = {v[i].b + 1, v[i].x, v[i].t, i, true};
	}
	
	for(int i = 0; i < q; ++i) {
		fscanf(fin, "%d%d", &query[i].l, &query[i].y);
		query[i].rez = &rez[i];
		auxx[n + i] = query[i].l;
	}

	normalize(n + q);
	
	sort(event, event + 2 * n, cmp1);
	sort(query, query + q, cmp3);
	
	int lastup = 0, nTypes = 0;
	for(int i = 0; i < q; ++i) {
		while(lastup < 2 * n && event[lastup].time <= query[i].y) {
			if(event[lastup].scoate) {
				eraseStore(event[lastup].x, event[lastup].t, event[lastup].id);
				if(typestore[event[lastup].t].size() == 0)
					--nTypes;
			} else {
				addStore(event[lastup].x, event[lastup].t, event[lastup].id);
				if(typestore[event[lastup].t].size() == 1)
					++nTypes;
			}
			++lastup;
		}

		if(nTypes < k)
			*query[i].rez = -1;
		else {
			pair<int, int> rezQ = queryAint(getId(query[i].l), 1, transf.size(), 1);
			*query[i].rez = max(rezQ.second - query[i].l,
			                max(query[i].l - rezQ.first, 0));
		}
	}

	for(int i = 0; i < q; ++i)
		fprintf(fout, "%d\n", rez[i]);

#ifdef HOME
	fclose(fin);
	fclose(fout);
#endif
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:182:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d%d", &n, &k, &q);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:185:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d%d%d", &v[i].x, &v[i].t, &v[i].a, &v[i].b);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:192:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d%d", &query[i].l, &query[i].y);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 164792 KB Output is correct
2 Correct 150 ms 164792 KB Output is correct
3 Correct 146 ms 164792 KB Output is correct
4 Incorrect 147 ms 164924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 164792 KB Output is correct
2 Correct 150 ms 164792 KB Output is correct
3 Correct 146 ms 164792 KB Output is correct
4 Incorrect 147 ms 164924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5097 ms 445384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5129 ms 445384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 164792 KB Output is correct
2 Correct 150 ms 164792 KB Output is correct
3 Correct 146 ms 164792 KB Output is correct
4 Incorrect 147 ms 164924 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 164792 KB Output is correct
2 Correct 150 ms 164792 KB Output is correct
3 Correct 146 ms 164792 KB Output is correct
4 Incorrect 147 ms 164924 KB Output isn't correct
5 Halted 0 ms 0 KB -