oj.uz

답안 #685647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685647 2023-01-24T18:24:40 Z GusterGoose27 Sunčanje (COCI18_suncanje) C++11
0 / 130
 1040 ms 139328 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5;
const int MAXM = 2e5;
bool active[MAXN];
bool covered[MAXN];
vector<int> add[MAXM];
vector<int> del[MAXM];
vector<int> xval;
vector<int> yval;
map<int, int> convx;
map<int, int> convy;

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	priority_queue<int> actvals;
	priority_queue<int> actvals_contained;
	priority_queue<int, vector<int>, greater<int>> uncovered;
	priority_queue<int, vector<int>, greater<int>> uncovered_contained;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
		}
	}
	int cur_mx(priority_queue<int> &pq) {
		while (!pq.empty() && !active[pq.top()]) pq.pop();
		if (pq.empty()) return -1;
		return pq.top();
	}
	// int get_mx(int lv, int rv) {
	// 	if (lp > rv || rp < lv) return -1;
	// 	if (lp >= lv && rp <= rv) return cur_mx();
	// 	return max(l->get_mx(lv, rv), r->get_mx(lv, rv));
	// }
	void cover(int v, priority_queue<int, vector<int>, greater<int>> &pq) {
		while (!pq.empty() && (pq.top() < v || covered[pq.top()])) {
			covered[pq.top()] = 1;
			pq.pop();
		}
	}
	void ins(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			cover(v, uncovered_contained);
			if (cur_mx(actvals_contained) > v) covered[v] = 1;
			actvals.push(v);
			actvals_contained.push(v);
			if (!covered[v]) {
				uncovered.push(v);
				uncovered_contained.push(v);
			}
			return;
		}
		cover(v, uncovered);
		if (cur_mx(actvals) > v) covered[v] = 1;
		else uncovered_contained.push(v);
		actvals_contained.push(v);
		l->ins(lv, rv, v); r->ins(lv, rv, v);
	}
};

pii xs[MAXN];
pii ys[MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> xs[i].first >> ys[i].first >> xs[i].second >> ys[i].second;
		xs[i].second += xs[i].first;
		ys[i].second += ys[i].first;
		xval.push_back(xs[i].first);
		xval.push_back(xs[i].second);
		yval.push_back(ys[i].first);
		yval.push_back(ys[i].second);
	}
	sort(xval.begin(), xval.end());
	sort(yval.begin(), yval.end());
	for (int x: xval) {
		if (convx.find(x) == convx.end()) convx[x] = convx.size();
	}
	for (int y: yval) {
		if (convy.find(y) == convy.end()) convy[y] = convy.size();
	}
	for (int i = 0; i < n; i++) {
		add[convx[xs[i].first]].push_back(i);
		del[convx[xs[i].second]].push_back(i);
		ys[i].first = convy[ys[i].first];
		ys[i].second = convy[ys[i].second];
		// cout << ys[i].first << " " << ys[i].second << "\n";
	}
	stree *tree = new stree(0, convy.size()-1);
	for (int i = 0; i < convx.size(); i++) {
		for (int v: del[i]) {
			active[v] = 0;
		}
		for (int v: add[i]) {
			tree->ins(ys[v].first, ys[v].second-1, v);
			active[v] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		if (covered[i]) cout << "NE\n";
		else cout << "DA\n";
	}
}

Compilation message

suncanje.cpp: In function 'int main()':
suncanje.cpp:105:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for (int i = 0; i < convx.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 16300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 25808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 189 ms 38264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 233 ms 50560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 448 ms 74944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 450 ms 76772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 420 ms 78344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 683 ms 109464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 694 ms 116076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1040 ms 139328 KB Output isn't correct
2 Halted 0 ms 0 KB -