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 fi first
#define se second
const int N = 3e5 + 5;
struct reg{
int lx, ly, rx, ry;
} reg[N];
struct point{
int x, y, color;
} p[N];
int n,m,st[4*N],lazy[4*N],par[N],ans[N];
vector<int> dmx,dmy,add[N],sub[N],pnt[N],adj[N];
map<int,int> idx,idy;
set<int> s[N];
//IT seg
void push_down(int id,int l,int r){
if(lazy[id] != -1){
st[id] = lazy[id];
if(l < r){
lazy[id<<1] = lazy[id];
lazy[id<<1|1] = lazy[id];
}
lazy[id] = -1;
}
}
void update(int id,int l,int r,int i,int j,int val){
push_down(id, l, r);
if(l>j || r<i || i>j){
return;
}
if(l>=i && r<=j){
st[id] = val;
if(l < r){
lazy[id<<1] = val;
lazy[id<<1|1] = val;
}
return;
}
int mid = (l + r) >> 1;
update(id<<1, l, mid, i, j, val);
update(id<<1|1, mid+1, r, i, j, val);
st[id] = max(st[id<<1], st[id<<1|1]);
}
int get(int id,int l,int r,int i,int j){
push_down(id, l, r);
if(l>j || r<i || i>j){
return -1e9;
}
if(l>=i && r<=j){
return st[id];
}
int mid = (l + r) >> 1;
return max(get(id<<1, l, mid, i, j), get(id<<1|1, mid+1, r, i, j));
}
//gop set
void dfs(int u){
for(int v: adj[u]){
dfs(v);
}
for(int v: adj[u]){
if(s[u].size() < s[v].size()){
swap(s[u], s[v]);
}
}
for(int v: adj[u]){
for(int w: s[v]){
s[u].insert(w);
}
}
ans[u] = s[u].size();
}
//main
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> reg[i].lx >> reg[i].ly >> reg[i].rx >> reg[i].ry;
if(idx[reg[i].lx] == 0){
dmx.push_back(reg[i].lx);
idx[reg[i].lx] = 1;
}
if(idy[reg[i].ly] == 0){
dmy.push_back(reg[i].ly);
idy[reg[i].ly] = 1;
}
if(idx[reg[i].rx] == 0){
dmx.push_back(reg[i].rx);
idx[reg[i].rx] = 1;
}
if(idy[reg[i].ry] == 0){
dmy.push_back(reg[i].ry);
idy[reg[i].ry] = 1;
}
}
int dem = 0;
for(int i=1;i<=m;i++){
cin >> p[i].x >> p[i].y >> p[i].color;
if(idx[p[i].x] == 0){
dmx.push_back(p[i].x);
idx[p[i].x] = 1;
}
if(idy[p[i].y] == 0){
dmy.push_back(p[i].y);
idy[p[i].y] = 1;
}
}
sort(dmx.begin(), dmx.end());
sort(dmy.begin(), dmy.end());
for(int i=0;i<dmx.size();i++){
idx[dmx[i]] = i + 1;
}
for(int i=0;i<dmy.size();i++){
idy[dmy[i]] = i + 1;
}
for(int i=1;i<=n;i++){
reg[i].lx = idx[reg[i].lx]; reg[i].rx = idx[reg[i].rx];
reg[i].ly = idy[reg[i].ly]; reg[i].ry = idy[reg[i].ry];
add[reg[i].lx].push_back(i);
sub[reg[i].rx].push_back(i);
}
for(int i=1;i<=m;i++){
p[i].x = idx[p[i].x];
p[i].y = idy[p[i].y];
pnt[p[i].x].push_back(i);
}
int h = dmy.size(), len = dmx.size();
for(int i=1;i<=len;i++){
for(int j: add[i]){
int pre = get(1, 1, h, reg[j].ly, reg[j].ry);
adj[pre].push_back(j);
par[j] = pre;
update(1, 1, h, reg[j].ly, reg[j].ry, j);
}
for(int j: pnt[i]){
int now = get(1, 1, h, p[j].y, p[j].y);
s[now].insert(p[j].color);
}
for(int j: sub[i]){
update(1, 1, h, reg[j].ly, reg[j].ry, par[j]);
}
}
for(int i=1;i<=n;i++){
if(par[i] == 0){
dfs(i);
}
}
for(int i=1;i<=n;i++){
cout << ans[i] << "\n";
}
}
Compilation message (stderr)
plahte.cpp: In function 'int main()':
plahte.cpp:110:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dmx.size();i++){
~^~~~~~~~~~~
plahte.cpp:113:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<dmy.size();i++){
~^~~~~~~~~~~
plahte.cpp:96:6: warning: unused variable 'dem' [-Wunused-variable]
int dem = 0;
^~~
# | 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... |