This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) (int)x.size()
#define pb(x) push_back(x)
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 8e4 + 5, INF = 1e9;
struct event{
int x = 0, y1 = 0, y2 = 0, tip = 0, id = 0;
friend bool operator < (const event A, const event B){
if(A.x != B.x) return A.x < B.x;
if(A.y1 != B.y1) return A.y1 < B.y1;
return A.tip < B.tip;
}
};
int n, m;
event rectangles[MAXN];
vector <event> rectangle, v;
int par[MAXN];
vector <int> colors[MAXN], E[MAXN], boja;
void load(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
REP(i, n){
event a, b;
cin >> a.x >> a.y1 >> b.x >> b.y2;
a.y2 = b.y2; b.y1 = a.y1;
a.tip = -1; b.tip = 1;
a.id = b.id = i;
swap(b.y1, b.y2);
v.pb(a); v.pb(b);
rectangles[i] = a;
}
REP(i, m){
event a;
cin >> a.x >> a.y1 >> a.id;
boja.pb(a.id);
a.tip = 0;
v.pb(a);
}
}
void sweep(){
sort(v.begin(), v.end());
set<point> S;
for(auto it : v){
//cout << "tip " _ it.tip _ it.x _ it.y1 _ it.y2 _ "\n";
if(it.tip == -1){
auto pos = S.lower_bound(point(it.y1, -INF));
par[it.id] = -1;
if(pos != S.end() && rectangles[(*pos).second].y1 < it.y1 && rectangles[(*pos).second].y2 > it.y2){
par[it.id] = (*pos).second;
E[(*pos).second].pb(it.id);
}
else if(pos != S.end() && par[(*pos).second] != -1 && rectangles[par[(*pos).second]].y1 < it.y1 && rectangles[par[(*pos).second]].y2 > it.y2){
par[it.id] = par[(*pos).second];
E[par[(*pos).second]].pb(it.id);
}
S.insert(point(it.y1, it.id));
S.insert(point(it.y2, it.id));
}
else if(it.tip == 0){
auto pos = S.lower_bound(point(it.y1, -INF));
if(pos != S.end() && rectangles[(*pos).second].y1 <= it.y1 && rectangles[(*pos).second].y2 >= it.y1){
colors[(*pos).second].pb(it.id);
}
else if(pos != S.end() && par[(*pos).second] != -1 && rectangles[par[(*pos).second]].y1 <= it.y1 && rectangles[par[(*pos).second]].y2 >= it.y1){
colors[par[(*pos).second]].pb(it.id);
}
}
else{
S.erase(point(it.y1, it.id));
S.erase(point(it.y2, it.id));
}
}
sort(boja.begin(), boja.end());
boja.erase(unique(boja.begin(), boja.end()), boja.end());
REP(i, n)
for(auto &it : colors[i])
it = lower_bound(boja.begin(), boja.end(), it) - boja.begin();
}
int sz[MAXN];
void dfsSz(int x){
sz[x] = 1;
for(auto it : E[x]){
dfsSz(it);
sz[x] += sz[it];
}
}
bool heavy[MAXN];
int cnt, have[MAXN], sol[MAXN];
void add(int x, int val){
for(auto it : colors[x]){
have[it] += val;
if(val == 1 && have[it] == 1) cnt ++;
else if(val == -1 && have[it] == 0) cnt --;
}
for(auto it : E[x]){
if(heavy[it]) continue;
add(it, val);
}
}
void dfs(int x, bool isHeavy = false){
int mx = -1, mx_id = -1;
for(auto it : E[x]){
if(sz[it] > mx){
mx = sz[it];
mx_id = it;
}
}
for(auto it : E[x]){
if(it == mx_id) continue;
dfs(it, 0);
}
if(mx != -1){
dfs(mx_id, 1);
heavy[mx_id] = true;
}
add(x, 1);
sol[x] = cnt;
//cout << cnt _ x _ SOL[x] << " ZASTO\n";
if(mx != -1)
heavy[mx_id] = false;
if(!isHeavy){
add(x, -1);
}
}
int main(){
load();
sweep();
REP(i, n)
if(par[i] == -1){
dfsSz(i);
dfs(i);
}
REP(i, n)
cout << sol[i] << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |