oj.uz

Submission #685744

# Submission time Handle Problem Language Result Execution time Memory
685744 2023-01-25T00:10:46 Z GusterGoose27 Sunčanje (COCI18_suncanje) C++11
130 / 130
 867 ms 146556 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()] || !active[pq.top()])) {
			if (active[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-1;
		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, 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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16240 KB Output is correct
2 Correct 38 ms 19124 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 25480 KB Output is correct
2 Correct 334 ms 71756 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 37724 KB Output is correct
2 Correct 409 ms 85912 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 49424 KB Output is correct
2 Correct 317 ms 74176 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 73660 KB Output is correct
2 Correct 504 ms 91104 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 75216 KB Output is correct
2 Correct 436 ms 85444 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 77608 KB Output is correct
2 Correct 536 ms 94308 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 107856 KB Output is correct
2 Correct 426 ms 78568 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 113936 KB Output is correct
2 Correct 689 ms 119536 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 136396 KB Output is correct
2 Correct 864 ms 146556 KB Output is correct