oj.uz

Submission #106831

# Submission time Handle Problem Language Result Execution time Memory
106831 2019-04-20T16:32:27 Z polyfish New Home (APIO18_new_home) C++14
12 / 100
 5000 ms 128428 KB 
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "new_home"

const int MAX_N = 300002;
const int INF = 1e9+100;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct treap {

	struct item {
		int L, R, max_r, prior;
		item *l, *r;

		item(int L=0, int R=0): L(L), R(R) {
			max_r = R;
			prior = uniform_int_distribution<int>(1, INF)(rng);
//			prior = 1;
            l = r = nullptr;
		}
	};

	typedef item * pitem;

	pitem root = nullptr;

	int get_max_r(pitem t) {
		return t ? t->max_r : 0;
	}

	void upd(pitem t) {
		if (t)
			t->max_r = max(t->R, max(get_max_r(t->l), get_max_r(t->r)));
	}

	void split(pitem t, pitem &l, pitem &r, int key) {
		if (!t) {
			l = r = nullptr;
		}
		else {
			if (key>t->L)
				split(t->r, t->r, r, key), l = t;
			else
				split(t->l, l, t->l, key), r = t;
		}

		upd(t);
	}

	void merge(pitem &t, pitem l, pitem r) {
		if (!l || !r) {
			t = l ? l : r;
		}
		else {
			if (l->prior>r->prior)
				merge(l->r, l->r, r), t = l;
			else
				merge(r->l, l, r->l), t = r;
		}

		upd(t);
	}

	void insert(pitem &t, pitem it) {
		if (!t) {
			t = it;
		}
		else {
			if (it->prior>t->prior)
				split(t, it->l, it->r, it->L), t = it;
			else
				insert(it->L<t->L ? t->l : t->r, it);
		}

		upd(t);
	}

	void erase(pitem &t, int L, int R) {
		if (!t)
			return;

		if (t->L==L && t->R==R)
			merge(t, t->l, t->r);
		else
			erase(L<t->L ? t->l : t->r, L, R);

		upd(t);
	}

	int get(pitem t, int L) {
		if (!t)
			return -INF;

		if (L<t->L)
			return get(t->l, L);

		return max(max(t->R, get_max_r(t->l)), get(t->r, L));
	}

	void insert(int L, int R) {
		insert(root, new item(L, R));
	}

	void erase(int L, int R) {
		erase(root, L, R);
	}

	int get(int L) {
		return get(root, L);
	}
};

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

struct query {
	int l, y;
};

int n, k, nQueries, res[MAX_N];
vector<int> T, store_event[MAX_N*3], q[MAX_N*3];
store s[MAX_N];
query Q[MAX_N];
map<int, int> pos[MAX_N*3];
treap interval_set;

int read_int() {
    char c;

    for (c = getchar(); c<'0' || c>'9'; c = getchar());

    int res = c - '0';

    for (c = getchar(); '0'<=c && c<='9'; c = getchar())
        res = res * 10 + c - '0';

    return res;
}

void read_input() {
	n = read_int();
	k = read_int();
	nQueries = read_int();

	for (int i=1; i<=n; ++i) {
        s[i].x = read_int();
        s[i].t = read_int();
        s[i].a = read_int();
        s[i].b = read_int();
	}

	for (int i=1; i<=nQueries; ++i) {
		Q[i].l = read_int();
		Q[i].y = read_int();
	}
}

void compress() {
	for (int i=1; i<=n; ++i) {
		T.push_back(s[i].a);
		T.push_back(s[i].b);
	}

	for (int i=1; i<=nQueries; ++i)
		T.push_back(Q[i].y);

	sort(T.begin(), T.end());
	T.resize(unique(T.begin(), T.end()) - T.begin());

	#define get_pos(P, x) lower_bound(P.begin(), P.end(), x) - P.begin() + 1
	for (int i=1; i<=n; ++i) {
		s[i].a = get_pos(T, s[i].a);
		s[i].b = get_pos(T, s[i].b);
	}

	for (int i=1; i<=nQueries; ++i)
		Q[i].y = get_pos(T, Q[i].y);
	#undef uniq
}

void init() {
	for (int i=1; i<=n; ++i) {
		store_event[s[i].a].push_back(i);
		store_event[s[i].b+1].push_back(-i);
	}

	for (int i=1; i<=nQueries; ++i) {
		q[Q[i].y].push_back(i);
	}

	for (int i=1; i<=k; ++i) {
		++pos[i][-INF];
		++pos[i][INF];
		interval_set.insert(-INF, INF);
	}
}

void add_store(int idx) {
	int tmp = ++pos[s[idx].t][s[idx].x];

	if (tmp==1) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//		debug(u->first);
//        debug(v->first);

		interval_set.erase(u->first, v->first);
		interval_set.insert(u->first, s[idx].x);
		interval_set.insert(s[idx].x, v->first);
	}
}

void remove_store(int idx) {
	int tmp = --pos[s[idx].t][s[idx].x];

	if (!tmp) {
		auto u = pos[s[idx].t].lower_bound(s[idx].x);
		--u;
		auto v = pos[s[idx].t].upper_bound(s[idx].x);
//        debug(u->first);
//        debug(v->first);

		interval_set.erase(u->first, s[idx].x);
		interval_set.erase(s[idx].x, v->first);
		interval_set.insert(u->first, v->first);
        pos[s[idx].t].erase(s[idx].x);
	}
}

int bisect(int x) {
	int l = 0, r = 2e8;

	for (int mid=(l+r)/2; mid!=l && r!=mid; mid=(l+r)/2) {
		if (interval_set.get(x-mid-1)>x+mid)
			l = mid;
		else
			r = mid;
	}

	for (int i=l; i<=r; ++i) {
		if (interval_set.get(x-i-1)<=x+i)
			return i;
	}

	return -1;
}

void solve() {

	for (int i=1; i<=T.size(); ++i) {
		for (auto x : store_event[i]) {
			if (x>0)
				add_store(x);
			else
				remove_store(-x);
		}

		for (auto x : q[i])
			res[x] = bisect(Q[x].l);
	}

	for (int i=1; i<=nQueries; ++i)
		cout << res[i] << '\n';
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
//		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);

	read_input();
	compress();
	init();
	solve();
}

Compilation message

new_home.cpp: In function 'void solve()':
new_home.cpp:260:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<=T.size(); ++i) {
                ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 84984 KB Output is correct
2 Correct 90 ms 84984 KB Output is correct
3 Correct 85 ms 84984 KB Output is correct
4 Correct 87 ms 84984 KB Output is correct
5 Correct 85 ms 85040 KB Output is correct
6 Correct 93 ms 84960 KB Output is correct
7 Correct 116 ms 85116 KB Output is correct
8 Correct 102 ms 85104 KB Output is correct
9 Correct 111 ms 85140 KB Output is correct
10 Correct 86 ms 85112 KB Output is correct
11 Correct 93 ms 84980 KB Output is correct
12 Correct 86 ms 84984 KB Output is correct
13 Correct 88 ms 85112 KB Output is correct
14 Correct 90 ms 85032 KB Output is correct
15 Correct 88 ms 85080 KB Output is correct
16 Correct 91 ms 85092 KB Output is correct
17 Correct 93 ms 84984 KB Output is correct
18 Correct 102 ms 85228 KB Output is correct
19 Correct 95 ms 85112 KB Output is correct
20 Correct 99 ms 85112 KB Output is correct
21 Correct 106 ms 85112 KB Output is correct
22 Correct 110 ms 85172 KB Output is correct
23 Correct 102 ms 85032 KB Output is correct
24 Correct 89 ms 85292 KB Output is correct
25 Correct 84 ms 85088 KB Output is correct
26 Correct 88 ms 84956 KB Output is correct
27 Correct 87 ms 85112 KB Output is correct
28 Correct 98 ms 85084 KB Output is correct
29 Correct 83 ms 84992 KB Output is correct
30 Correct 81 ms 84984 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 84984 KB Output is correct
2 Correct 90 ms 84984 KB Output is correct
3 Correct 85 ms 84984 KB Output is correct
4 Correct 87 ms 84984 KB Output is correct
5 Correct 85 ms 85040 KB Output is correct
6 Correct 93 ms 84960 KB Output is correct
7 Correct 116 ms 85116 KB Output is correct
8 Correct 102 ms 85104 KB Output is correct
9 Correct 111 ms 85140 KB Output is correct
10 Correct 86 ms 85112 KB Output is correct
11 Correct 93 ms 84980 KB Output is correct
12 Correct 86 ms 84984 KB Output is correct
13 Correct 88 ms 85112 KB Output is correct
14 Correct 90 ms 85032 KB Output is correct
15 Correct 88 ms 85080 KB Output is correct
16 Correct 91 ms 85092 KB Output is correct
17 Correct 93 ms 84984 KB Output is correct
18 Correct 102 ms 85228 KB Output is correct
19 Correct 95 ms 85112 KB Output is correct
20 Correct 99 ms 85112 KB Output is correct
21 Correct 106 ms 85112 KB Output is correct
22 Correct 110 ms 85172 KB Output is correct
23 Correct 102 ms 85032 KB Output is correct
24 Correct 89 ms 85292 KB Output is correct
25 Correct 84 ms 85088 KB Output is correct
26 Correct 88 ms 84956 KB Output is correct
27 Correct 87 ms 85112 KB Output is correct
28 Correct 98 ms 85084 KB Output is correct
29 Correct 83 ms 84992 KB Output is correct
30 Correct 81 ms 84984 KB Output is correct
31 Correct 2501 ms 102000 KB Output is correct
32 Correct 185 ms 88428 KB Output is correct
33 Correct 870 ms 101488 KB Output is correct
34 Correct 2387 ms 101680 KB Output is correct
35 Correct 1425 ms 102016 KB Output is correct
36 Correct 1213 ms 101984 KB Output is correct
37 Correct 585 ms 101412 KB Output is correct
38 Correct 554 ms 101512 KB Output is correct
39 Correct 358 ms 101444 KB Output is correct
40 Correct 441 ms 101396 KB Output is correct
41 Correct 1603 ms 101588 KB Output is correct
42 Correct 3349 ms 101496 KB Output is correct
43 Correct 3228 ms 89308 KB Output is correct
44 Correct 1346 ms 101684 KB Output is correct
45 Correct 644 ms 101648 KB Output is correct
46 Correct 318 ms 101360 KB Output is correct
47 Correct 354 ms 100720 KB Output is correct
48 Correct 304 ms 100588 KB Output is correct
49 Correct 345 ms 100844 KB Output is correct
50 Correct 1463 ms 101392 KB Output is correct
51 Correct 336 ms 100844 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 112792 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 5102 ms 128428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 84984 KB Output is correct
2 Correct 90 ms 84984 KB Output is correct
3 Correct 85 ms 84984 KB Output is correct
4 Correct 87 ms 84984 KB Output is correct
5 Correct 85 ms 85040 KB Output is correct
6 Correct 93 ms 84960 KB Output is correct
7 Correct 116 ms 85116 KB Output is correct
8 Correct 102 ms 85104 KB Output is correct
9 Correct 111 ms 85140 KB Output is correct
10 Correct 86 ms 85112 KB Output is correct
11 Correct 93 ms 84980 KB Output is correct
12 Correct 86 ms 84984 KB Output is correct
13 Correct 88 ms 85112 KB Output is correct
14 Correct 90 ms 85032 KB Output is correct
15 Correct 88 ms 85080 KB Output is correct
16 Correct 91 ms 85092 KB Output is correct
17 Correct 93 ms 84984 KB Output is correct
18 Correct 102 ms 85228 KB Output is correct
19 Correct 95 ms 85112 KB Output is correct
20 Correct 99 ms 85112 KB Output is correct
21 Correct 106 ms 85112 KB Output is correct
22 Correct 110 ms 85172 KB Output is correct
23 Correct 102 ms 85032 KB Output is correct
24 Correct 89 ms 85292 KB Output is correct
25 Correct 84 ms 85088 KB Output is correct
26 Correct 88 ms 84956 KB Output is correct
27 Correct 87 ms 85112 KB Output is correct
28 Correct 98 ms 85084 KB Output is correct
29 Correct 83 ms 84992 KB Output is correct
30 Correct 81 ms 84984 KB Output is correct
31 Correct 2501 ms 102000 KB Output is correct
32 Correct 185 ms 88428 KB Output is correct
33 Correct 870 ms 101488 KB Output is correct
34 Correct 2387 ms 101680 KB Output is correct
35 Correct 1425 ms 102016 KB Output is correct
36 Correct 1213 ms 101984 KB Output is correct
37 Correct 585 ms 101412 KB Output is correct
38 Correct 554 ms 101512 KB Output is correct
39 Correct 358 ms 101444 KB Output is correct
40 Correct 441 ms 101396 KB Output is correct
41 Correct 1603 ms 101588 KB Output is correct
42 Correct 3349 ms 101496 KB Output is correct
43 Correct 3228 ms 89308 KB Output is correct
44 Correct 1346 ms 101684 KB Output is correct
45 Correct 644 ms 101648 KB Output is correct
46 Correct 318 ms 101360 KB Output is correct
47 Correct 354 ms 100720 KB Output is correct
48 Correct 304 ms 100588 KB Output is correct
49 Correct 345 ms 100844 KB Output is correct
50 Correct 1463 ms 101392 KB Output is correct
51 Correct 336 ms 100844 KB Output is correct
52 Execution timed out 5030 ms 97680 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 84984 KB Output is correct
2 Correct 90 ms 84984 KB Output is correct
3 Correct 85 ms 84984 KB Output is correct
4 Correct 87 ms 84984 KB Output is correct
5 Correct 85 ms 85040 KB Output is correct
6 Correct 93 ms 84960 KB Output is correct
7 Correct 116 ms 85116 KB Output is correct
8 Correct 102 ms 85104 KB Output is correct
9 Correct 111 ms 85140 KB Output is correct
10 Correct 86 ms 85112 KB Output is correct
11 Correct 93 ms 84980 KB Output is correct
12 Correct 86 ms 84984 KB Output is correct
13 Correct 88 ms 85112 KB Output is correct
14 Correct 90 ms 85032 KB Output is correct
15 Correct 88 ms 85080 KB Output is correct
16 Correct 91 ms 85092 KB Output is correct
17 Correct 93 ms 84984 KB Output is correct
18 Correct 102 ms 85228 KB Output is correct
19 Correct 95 ms 85112 KB Output is correct
20 Correct 99 ms 85112 KB Output is correct
21 Correct 106 ms 85112 KB Output is correct
22 Correct 110 ms 85172 KB Output is correct
23 Correct 102 ms 85032 KB Output is correct
24 Correct 89 ms 85292 KB Output is correct
25 Correct 84 ms 85088 KB Output is correct
26 Correct 88 ms 84956 KB Output is correct
27 Correct 87 ms 85112 KB Output is correct
28 Correct 98 ms 85084 KB Output is correct
29 Correct 83 ms 84992 KB Output is correct
30 Correct 81 ms 84984 KB Output is correct
31 Correct 2501 ms 102000 KB Output is correct
32 Correct 185 ms 88428 KB Output is correct
33 Correct 870 ms 101488 KB Output is correct
34 Correct 2387 ms 101680 KB Output is correct
35 Correct 1425 ms 102016 KB Output is correct
36 Correct 1213 ms 101984 KB Output is correct
37 Correct 585 ms 101412 KB Output is correct
38 Correct 554 ms 101512 KB Output is correct
39 Correct 358 ms 101444 KB Output is correct
40 Correct 441 ms 101396 KB Output is correct
41 Correct 1603 ms 101588 KB Output is correct
42 Correct 3349 ms 101496 KB Output is correct
43 Correct 3228 ms 89308 KB Output is correct
44 Correct 1346 ms 101684 KB Output is correct
45 Correct 644 ms 101648 KB Output is correct
46 Correct 318 ms 101360 KB Output is correct
47 Correct 354 ms 100720 KB Output is correct
48 Correct 304 ms 100588 KB Output is correct
49 Correct 345 ms 100844 KB Output is correct
50 Correct 1463 ms 101392 KB Output is correct
51 Correct 336 ms 100844 KB Output is correct
52 Execution timed out 5042 ms 112792 KB Time limit exceeded
53 Halted 0 ms 0 KB -