Submission #575298

#	Time	Username	Problem	Language	Result	Execution time	Memory
575298		penguinhacker	Sunčanje (COCI18_suncanje)	C++14	130 / 130	494 ms	43564 KiB

suncanje

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

#define ar array

const int mxN=1e5, INF=1e9;
int n, node_mn[1<<19], node_mx[1<<19], all_mn[1<<19], all_mx[1<<19];
set<int> s[1<<19];
ar<int, 2> ys[mxN];
bool ans[mxN];
vector<int> dy;

void bld(int u=1, int l=0, int r=dy.size()-1) {
	node_mn[u]=all_mn[u]=INF;
	node_mx[u]=all_mx[u]=-1;
	if (l==r) return;
	int mid=(l+r)/2;
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
}

void pll(int u, int l, int r) {
	node_mn[u]=s[u].size()?*s[u].begin():INF;
	node_mx[u]=s[u].size()?*s[u].rbegin():-1;
	if (l!=r) {
		all_mn[u]=min({node_mn[u], all_mn[2*u], all_mn[2*u+1]});
		all_mx[u]=max({node_mx[u], all_mx[2*u], all_mx[2*u+1]});
	} else
		all_mn[u]=node_mn[u], all_mx[u]=node_mx[u];
}

void upd(int i, bool del, int u=1, int l=0, int r=dy.size()-1) {
	if (ys[i][0]<=l&&r<=ys[i][1]) {
		if (!del) s[u].insert(i);
		else s[u].erase(i);
		pll(u, l, r);
		return;
	}
	int mid=(l+r)/2;
	if (ys[i][0]<=mid) upd(i, del, 2*u, l, mid);
	if (ys[i][1]>mid) upd(i, del, 2*u+1, mid+1, r);
	pll(u, l, r);
}

int qry(int i, bool mx, int u=1, int l=0, int r=dy.size()-1) {
	if (ys[i][0]<=l&&r<=ys[i][1])
		return mx?all_mx[u]:all_mn[u];
	int mid=(l+r)/2;
	int ls=ys[i][0]<=mid?qry(i, mx, 2*u, l, mid):(mx?-1:INF);
	int rs=ys[i][1]>mid?qry(i, mx, 2*u+1, mid+1, r):(mx?-1:INF);
	return mx?max({node_mx[u], ls, rs}):min({node_mn[u], ls, rs});
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	vector<ar<int, 4>> rects;
	for (int i=0; i<n; ++i) {
		int x, y, a, b;
		cin >> x >> y >> a >> b;
		dy.push_back(y);
		dy.push_back(y+b-1);
		rects.push_back({x, y, x+a-1, y+b-1});
	}
	sort(dy.begin(), dy.end());
	dy.resize(unique(dy.begin(), dy.end())-dy.begin());
	for (ar<int, 4>& rect : rects) {
		rect[1]=lower_bound(dy.begin(), dy.end(), rect[1])-dy.begin();
		rect[3]=lower_bound(dy.begin(), dy.end(), rect[3])-dy.begin();
	}
	vector<ar<int, 3>> events;
	for (int i=0; i<n; ++i) {
		ys[i]={rects[i][1], rects[i][3]};
		events.push_back({rects[i][0], 1, i});
		events.push_back({rects[i][2], 2, i});
	}
	sort(events.begin(), events.end());
	bld();
	for (auto& event : events) {
		int type=event[1], i=event[2];
		if (type==1) {
			ans[i]=qry(i, 1)>i;
			upd(i, 0);
		} else
			upd(i, 1);
	}
	for (auto& event : events) {
		int type=event[1], i=event[2];
		if (type==1) {
			for (int x=qry(i, 0); x<i; x=qry(i, 0))
				ans[x]=1, upd(x, 1);
			if (!ans[i]) upd(i, 0);
		} else if (!ans[i]) upd(i, 1);
	}
	for (int i=0; i<n; ++i)
		cout << (ans[i]?"NE":"DA") << "\n";
	return 0;
}

• 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