oj.uz

Submission #200088

# Submission time Handle Problem Language Result Execution time Memory
200088 2020-02-05T10:16:23 Z Saboon Sunčanje (COCI18_suncanje) C++14
130 / 130
 1967 ms 154556 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 79480 KB Output is correct
2 Correct 91 ms 80888 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 82936 KB Output is correct
2 Correct 674 ms 108532 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 87288 KB Output is correct
2 Correct 942 ms 118732 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 92152 KB Output is correct
2 Correct 748 ms 112244 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 106740 KB Output is correct
2 Correct 975 ms 119436 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 104176 KB Output is correct
2 Correct 969 ms 119536 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 856 ms 113516 KB Output is correct
2 Correct 886 ms 109616 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1315 ms 132460 KB Output is correct
2 Correct 713 ms 104692 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1408 ms 129760 KB Output is correct
2 Correct 1497 ms 139064 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1613 ms 131784 KB Output is correct
2 Correct 1967 ms 154556 KB Output is correct