Submission #200088

#	Time	Username	Problem	Language	Result	Execution time	Memory
200088		Saboon	Sunčanje (COCI18_suncanje)	C++14	130 / 130	1967 ms	154556 KiB

suncanje

#include <bits/stdc++.h>
#define spii set<pair<int,int>>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;

struct rectangle{
	int x1;
	int y1;
	int x2;
	int y2;
	rectangle(int x1_ = 0, int y1_ = 0, int x2_ = 0, int y2_ = 0){
		x1 = x1_, y1 = y1_, x2 = x2_, y2 = y2_;
	}
} r[maxn];

bool ans[maxn];

spii::iterator Left(spii &s, int l){
    auto it = s.lower_bound({l, -1});
    if (it != s.begin()){
        it --;
        if (it->second >= l)
            return (it);
        it ++;
    }
    return (it);
}
spii::iterator Right(spii &s, int r){
    return (s.lower_bound({r, -1}));
}

void add(spii &s, int l, int r){
	int nl = l, nr = r;
	auto le = Left(s, l), ri = Right(s, r);
	while (le != ri){
		ri --;
		nl = min(nl, le->first);
		nr = max(nr, ri->second);
		ri ++; s.erase(le, ri);
		le = Left(s, l), ri = Right(s, r);
	}
	s.insert({nl, nr});
}

bool get(spii &s, int l, int r){
	return Left(s, l) != Right(s, r);
}

set<pair<int,int>> s[2][8 * maxn];
bool add(int id, int L, int R, int l, int r, int lo, int hi){
	if (r <= L or R <= l)
		return 0;
	if (l <= L and R <= r){
		bool w = get(s[0][id], lo, hi) | get(s[1][id], lo, hi);
		add(s[0][id], lo, hi);
		return w;
	}
	add(s[1][id], lo, hi);
	int mid = (L + R) >> 1;
	bool w = 0;
	w |= add(2 * id + 0, L, mid, l, r, lo, hi);
	w |= add(2 * id + 1, mid, R, l, r, lo, hi);
	return (w | get(s[0][id], lo, hi));
}

int main(){ 
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> cmp;
	for (int i = 0; i < n; i++){
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		r[i] = rectangle(x, y, x+a, y+b);
		cmp.push_back(x);
		cmp.push_back(x+a);
	}
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	int m = cmp.size();
	for (int i = n - 1; i >= 0; i--){
		r[i].x1 = lower_bound(cmp.begin(), cmp.end(), r[i].x1) - cmp.begin();
		r[i].x2 = lower_bound(cmp.begin(), cmp.end(), r[i].x2) - cmp.begin();
		ans[i] = add(1, 0, m, r[i].x1, r[i].x2, r[i].y1, r[i].y2);
	}
	for (int i = 0; i < n; i++)
		cout << (ans[i] == 1 ? "NE\n" : "DA\n");
}

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