oj.uz

Submission #35609

# Submission time Handle Problem Language Result Execution time Memory
35609 2017-11-26T04:57:14 Z szawinis Plahte (COCI17_plahte) C++14
160 / 160
 789 ms 63632 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 8e4+10;
 
struct segtree {
	int n;
	vector<priority_queue<pair<int,int>>> t;
	segtree(int n): n(n) {
		t.resize(2*n);
		for(int i = 1; i < 2*n; i++) t[i].emplace(-1, N-1);
	}
	void push(int l, int r, int id, int tt) {
		++r;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) t[l++].emplace(tt, id);
			if(r & 1) t[--r].emplace(tt, id);
		}
	}
	void pop(int l, int r) {
		++r;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) t[l++].pop();
			if(r & 1) t[--r].pop();
		}
	}
	int query(int i) {
		pair<int,int> res = {-1, N-1};
		for(i += n; i >= 1; i >>= 1) res = max(t[i].top(), res);
		return res.second;
	}
};
 
struct query {
	int x, b, c, tp, id;
	bool operator<(const query& rhs) const {
		return (x < rhs.x || (x == rhs.x && tp < rhs.tp));
	}
};
 
int n, m, res[N];
vector<query> queries;
unordered_set<int> ls[N];
vector<int> ys, g[N];
 
void compress() {
	for(query q: queries) {
		ys.push_back(q.b);
		if(q.tp) ys.push_back(q.c);
	}
	sort(ys.begin(), ys.end());
	ys.resize(distance(ys.begin(), unique(ys.begin(), ys.end())));
	map<int,int> mp;
	for(int i = 0; i < ys.size(); i++) mp[ys[i]] = i;
	for(query& q: queries) {
		q.b = mp[q.b];
		if(q.tp) q.c = mp[q.c];
	}
}
 
void dfs(int u) {
	for(int v: g[u]) {
		dfs(v);
		if(ls[v].size() > ls[u].size()) swap(ls[u], ls[v]);
		for(int c: ls[v]) ls[u].insert(c);
		ls[v].clear();
	}
	res[u] = ls[u].size();
}
 
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0, a, b, c, d; i < n; i++) {
		scanf("%d %d %d %d", &a, &b, &c, &d);
		queries.push_back({a, b, d, -1, i});
		queries.push_back({c, b, d, 1, i});
	}
	for(int i = 0, a, b, c; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		queries.push_back({a, b, c, 0, i});
	}
	sort(queries.begin(), queries.end());
	compress();
	segtree st = segtree(ys.size());
	for(int t = 0; t < queries.size(); t++) {
		query q = queries[t];
		if(q.tp == -1) {
			g[st.query(q.b)].push_back(q.id);
			st.push(q.b, q.c, q.id, t);
		} else if(q.tp == 1) {
			st.pop(q.b, q.c);
		} else {
			int id = st.query(q.b);
			ls[id].insert(q.c);
		}
	}
	dfs(N-1);
	for(int i = 0; i < n; i++) printf("%d\n", res[i]);
}
// root node is N-1

Compilation message

plahte.cpp: In function 'void compress()':
plahte.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ys.size(); i++) mp[ys[i]] = i;
                   ^
plahte.cpp: In function 'int main()':
plahte.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t = 0; t < queries.size(); t++) {
                   ^
plahte.cpp:71:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
plahte.cpp:73:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &a, &b, &c, &d);
                                       ^
plahte.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &b, &c);
                                ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 22848 KB Output is correct
2 Correct 176 ms 22144 KB Output is correct
3 Correct 0 ms 8600 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 28292 KB Output is correct
2 Correct 213 ms 25512 KB Output is correct
3 Correct 3 ms 8600 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 44212 KB Output is correct
2 Correct 409 ms 34908 KB Output is correct
3 Correct 3 ms 8600 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 63632 KB Output is correct
2 Correct 746 ms 49752 KB Output is correct
3 Correct 3 ms 8600 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 789 ms 59900 KB Output is correct
2 Correct 753 ms 45232 KB Output is correct
3 Correct 0 ms 8600 KB Output is correct