Submission #88080

#	Time	Username	Problem	Language	Result	Execution time	Memory
88080		ImaniAm	Sunčanje (COCI18_suncanje)	C++14	0 / 130	494 ms	263168 KiB

suncanje

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef pair <int, int> pii;

const int maxn = 1e5 + 10, maxt = 2e5 + 10, maxs = (1 << 19) + 1, inf = 1e9 + 10;
set <pii> st[maxs][2];
int n, t[maxt], pos;
vector <pii> vec;
bool ans[maxn];

void addst(int id, int ind, pii p) {
	auto it = st[id][ind].upper_bound({p.first, inf}); it--;
	if (it->second >= p.second)
		return;
	if (it->second < p.first) {
		++it;
		if (it->first > p.second) {
			st[id][ind].insert(p);
			return;
		}
	}
	int l = min(p.first, it->first);
	for (; it->first <= p.second; ++it)
		vec.pb(*it);
	--it;
	int r = max(p.second, it->second);
	for (auto i: vec)
		st[id][ind].erase(i);
	vec.clear();
	st[id][ind].insert({l, r});
	return;
}

inline void add(int l, int r, int &x, int &x2, int &y, int &y2, int id) {
	if (l >= x2 || x >= r)
		return;
	addst(id, 1, {y, y2});
	if (l >= x && r <= x2) {
		addst(id, 0, {y, y2});
		return;
	}
	int mid = (l + r) >> 1, left = id << 1, right = left | 1;
	add(l, mid, x, x2, y, y2, left);
	add(mid, r, x, x2, y, y2, right);
	return;
}

bool check(int id, int ind, pii p) {
	auto it = st[id][ind].upper_bound({p.first, inf});
	if (it->first <= p.second)
		return true;
	--it;
	if (it->second >= p.first)
		return true;
	return false;
}

inline bool query(int l, int r, int &x, int &x2, int &y, int &y2, int id) {
	if (l >= x2 || x >= r)
		return false;
	if (check(id, 0, {y, y2}))
		return true;
	if (l >= x && r <= x2)
		return check(id, 1, {y, y2});
	int mid = (l + r) >> 1, left = id << 1, right = left | 1;
	return query(l, mid, x, x2, y, y2, left) || query(mid, r, x, x2, y, y2, right);
}

pair <pii, pii> p[maxn];

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> p[i].first.first >> p[i].first.second >> p[i].second.first >> p[i].second.second;
		p[i].second.first += p[i].first.first - 1;
		p[i].second.second += p[i].first.second - 1;
		t[pos++] = p[i].first.first;
		t[pos++] = p[i].second.first;
	}
	sort(t, t + pos);
	pos = unique(t, t + pos) - t;
	for (int i = 1; i < maxs; ++i)
		for (int j = 0; j < 2; ++j) {
			st[i][j].insert({-1, -1});
			st[i][j].insert({inf, inf});
		}
	for (int i = n - 1; ~i; --i) {
		p[i].first.first = lower_bound(t, t + pos, p[i].first.first) - t;
		p[i].second.first = lower_bound(t, t + pos, p[i].second.first) - t + 1;
		ans[i] = query(0, pos, p[i].first.first, p[i].second.first, p[i].first.second, p[i].second.second, 1);
		add(0, pos, p[i].first.first, p[i].second.first, p[i].first.second, p[i].second.second, 1);
	}
	for (int i = 0; i < n; ++i)
		if (ans[i])
			cout << "NE\n";
		else
			cout << "DA\n";
	return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13