#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define MAXN 80010
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();
template <int K> struct SegmentTree {
int SZ = 1 << K;
/**/
stack <pii> data[(1 << K) * 2]; // <id, time>
void update(int a, int b, pii x) { // add x to [a,b]
update(1, 0, SZ - 1, a, b, x);
}
void update(int node, int l, int r, int a, int b, pii x) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
data[node].push(x);
return;
}
int mid = (l + r) / 2;
update(node * 2, l, mid, a, b, x);
update(node * 2 + 1, mid + 1, r, a, b, x);
}
void ddelete(int a, int b, pii x) {
ddelete(1, 0, SZ - 1, a, b, x);
}
void ddelete(int node, int l, int r, int a, int b, pii x) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
// assert(data[node].top().first == x.first);
data[node].pop();
return;
}
int mid = (l + r) / 2;
ddelete(node * 2, l, mid, a, b, x);
ddelete(node * 2 + 1, mid + 1, r, a, b, x);
}
int query(int node) {
node += SZ;
pii ret = { -1,-1 }; // id, time
while (node) {
if (!data[node].empty()) {
if (data[node].top().second > ret.second) {
ret = data[node].top();
}
}
node /= 2;
}
return ret.first;
}
/**/
/**
stack<pii> fakeSeg[100000]; // <id, time>
void update(int a, int b, pii x) { // add x to [a,b]
FORE(i, a, b)
fakeSeg[i].push(x);
}
void ddelete(int a, int b, pii x) {
FORE(i, a, b) {
assert(fakeSeg[i].top().first == x.first);
fakeSeg[i].pop();
}
}
int query(int node) {
if (fakeSeg[node].size() == 0)
return -1;
return fakeSeg[node].top().first;
}
/**/
};
SegmentTree<18> tree;
/**
int main() {
io();
int N;
cin >> N;
FOR(i, 0, N) {
int type;
cin >> type;
if (type == 0) { // add
int a, b, x;
cin >> a >> b >> x;
tree.update(a, b, { x,i });
}
else if (type == 1) { // remove
int a, b, x;
cin >> a >> b >> x;
tree.ddelete(a, b, { x,i });
}
else { // query
int a;
cin >> a;
cout << tree.query(a) << "\n";
}
}
}
/**/
struct Event {
int x, f, y1, y2, id;
Event(int a, int b, int c, int d, int e) : x(a), f(b), y1(c), y2(d), id(e) {}
bool operator< (const Event& other) const {
return mp(x, f) < mp(other.x, other.f);
}
};
int N, M; // rect, balls
v<Event> allevents;
void compressCoord() {
map<int, int> conv;
FOR(i, 0, allevents.size()) {
conv[allevents[i].y1] = 0;
conv[allevents[i].y2] = 0;
}
int num = 0;
for (auto& en : conv)
en.second = num++;
FOR(i, 0, allevents.size()) {
allevents[i].y1 = conv[allevents[i].y1];
allevents[i].y2 = conv[allevents[i].y2];
}
}
void input() {
cin >> N >> M;
allevents.push_back(Event(-1, -1, -1, 1000000001, 0)); // start
allevents.push_back(Event(1000000001, 1, -1, 1000000001, 0)); // end
FOR(i, 0, N) {
int x1, y1, x2, y2, id = i + 1;
cin >> x1 >> y1 >> x2 >> y2;
allevents.push_back(Event(x1, -1, y1, y2, id)); // start
allevents.push_back(Event(x2, 1, y1, y2, id)); // end
}
FOR(i, 0, M) {
int x, y, c;
cin >> x >> y >> c;
allevents.push_back(Event(x, 0, y, -1, c));
}
}
int par[MAXN];
v<int> adj[MAXN];
set<int> colors[MAXN];
int ans[MAXN];
void merge(set<int> &a, set<int> &b) {
if (a.size() > b.size()) { // merge b into a
a.insert(b.begin(), b.end());
b.clear();
}
else { // merge a into b then swap
b.insert(a.begin(), a.end());
swap(a, b);
b.clear();
}
}
void dfs(int cur, int par) {
for (int chi : adj[cur]) if (chi != par) {
dfs(chi, cur);
merge(colors[cur], colors[chi]);
}
ans[cur] = colors[cur].size();
}
int main() {
io();
input();
compressCoord();
vsort(allevents);
FOR(i, 0, allevents.size()) {
Event e = allevents[i];
// cout << "lol\n";
if (e.f == -1) { // start
par[e.id] = tree.query((e.y1 + e.y2) / 2); // parent of e.id
tree.update(e.y1, e.y2, { e.id, i }); // add id into seg tree
}
else if (e.f == 1) { // end
tree.ddelete(e.y1, e.y2, { e.id, i });
}
else { // ball
colors[tree.query(e.y1)].insert(e.id); // which id is this ball in?
}
}
/* FORE(i, 0, N)
cout << i << ": " << par[i] << " par\n";
FORE(i, 0, N) {
cout << i << "contains: ";
for (int c : colors[i])
cout << c << " ";
cout << "\n";
}*/
FORE(i, 0, N) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
}
}
dfs(0, -1);
FORE(i, 1, N)
cout << ans[i] << "\n";
return 0;
}
/**/
void io() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
Compilation message
plahte.cpp:90:2: warning: "/*" within comment [-Wcomment]
/**/
plahte.cpp:118:1: warning: "/*" within comment [-Wcomment]
/**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
606 ms |
363984 KB |
Output is correct |
| 2 |
Correct |
644 ms |
363984 KB |
Output is correct |
| 3 |
Correct |
485 ms |
363984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
663 ms |
366348 KB |
Output is correct |
| 2 |
Correct |
712 ms |
366348 KB |
Output is correct |
| 3 |
Correct |
405 ms |
366348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
884 ms |
372020 KB |
Output is correct |
| 2 |
Correct |
873 ms |
372020 KB |
Output is correct |
| 3 |
Correct |
419 ms |
372020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1233 ms |
379484 KB |
Output is correct |
| 2 |
Correct |
1263 ms |
379484 KB |
Output is correct |
| 3 |
Correct |
421 ms |
379484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1228 ms |
379484 KB |
Output is correct |
| 2 |
Correct |
1162 ms |
379484 KB |
Output is correct |
| 3 |
Correct |
378 ms |
379484 KB |
Output is correct |
