oj.uz

Submission #575298

# Submission time Handle Problem Language Result Execution time Memory
575298 2022-06-10T06:18:15 Z penguinhacker Sunčanje (COCI18_suncanje) C++14
130 / 130
 494 ms 43564 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26196 KB Output is correct
2 Correct 32 ms 26380 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 27236 KB Output is correct
2 Correct 186 ms 33840 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 29408 KB Output is correct
2 Correct 245 ms 34800 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 30380 KB Output is correct
2 Correct 210 ms 33892 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 34340 KB Output is correct
2 Correct 261 ms 35100 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 34412 KB Output is correct
2 Correct 247 ms 34668 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 34360 KB Output is correct
2 Correct 278 ms 36280 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 41220 KB Output is correct
2 Correct 210 ms 34616 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 41708 KB Output is correct
2 Correct 362 ms 41728 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 43564 KB Output is correct
2 Correct 481 ms 43516 KB Output is correct