oj.uz

Submission #575251

# Submission time Handle Problem Language Result Execution time Memory
575251 2022-06-10T04:03:55 Z penguinhacker Sunčanje (COCI18_suncanje) C++14
130 / 130
 579 ms 44248 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#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> dx, 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;
		dx.push_back(x);
		dx.push_back(x+a-1);
		dy.push_back(y);
		dy.push_back(y+b-1);
		rects.push_back({x, y, x+a-1, y+b-1});
	}
	sort(dx.begin(), dx.end());
	sort(dy.begin(), dy.end());
	dx.resize(unique(dx.begin(), dx.end())-dx.begin());
	dy.resize(unique(dy.begin(), dy.end())-dy.begin());
	for (ar<int, 4>& rect : rects) {
		rect[0]=lower_bound(dx.begin(), dx.end(), rect[0])-dx.begin();
		rect[1]=lower_bound(dy.begin(), dy.end(), rect[1])-dy.begin();
		rect[2]=lower_bound(dx.begin(), dx.end(), rect[2])-dx.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) { // beginning of seg
			if (qry(i, 1)>i) // bigger time before
				ans[i]=1;
			upd(i, 0);
		} else { // end ?
			upd(i, 1);
		}
	}
	//cout << all_mn[1] << " " << all_mx[1] << endl;
	for (auto& event : events) {
		int type=event[1], i=event[2];
		if (type==1) {
			int x=qry(i, 0);
			while(x<i) {
				ans[x]=1;
				upd(x, 1);
				x=qry(i, 0);
			}
			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 27 ms 26188 KB Output is correct
2 Correct 49 ms 26416 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 27512 KB Output is correct
2 Correct 206 ms 34180 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 29600 KB Output is correct
2 Correct 461 ms 35220 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 30572 KB Output is correct
2 Correct 203 ms 34392 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 34644 KB Output is correct
2 Correct 346 ms 35568 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 34816 KB Output is correct
2 Correct 338 ms 35192 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 34708 KB Output is correct
2 Correct 397 ms 36852 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 41728 KB Output is correct
2 Correct 289 ms 35008 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 42300 KB Output is correct
2 Correct 509 ms 42340 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 44232 KB Output is correct
2 Correct 579 ms 44248 KB Output is correct