oj.uz

Submission #200087

# Submission time Handle Problem Language Result Execution time Memory
200087 2020-02-05T10:16:06 Z Saboon Sunčanje (COCI18_suncanje) C++14
0 / 130
 1602 ms 135128 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 ? "No\n" : "Yes\n");
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 79608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 83448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 88060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 93176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 825 ms 108468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 793 ms 105844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 870 ms 115316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1318 ms 134896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1446 ms 132440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1602 ms 135128 KB Output isn't correct
2 Halted 0 ms 0 KB -