oj.uz

Submission #35608

# Submission time Handle Problem Language Result Execution time Memory
35608 2017-11-26T04:55:07 Z szawinis Plahte (COCI17_plahte) C++14
0 / 160
 636 ms 63740 KB 
#include <bits/stdc++.h>
#define endl '\n'
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() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0, a, b, c, d; i < n; i++) {
		cin >> 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++) {
		cin >> 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++) cout << res[i] << endl;
}
// root node is N-1

Compilation message

plahte.cpp: In function 'void compress()':
plahte.cpp:54: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:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t = 0; t < queries.size(); t++) {
                   ^

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 159 ms 22964 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 209 ms 28408 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 413 ms 44332 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 636 ms 63740 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 619 ms 60020 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -