#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#ifdef LOCAL
const int mxN=100;
#else
const int mxN=3e5+5; //make sure this is right
#endif
const int mod=1e9+7;
struct RANK{
vector<int> all;
int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;}
void add(int x){all.pb(x);}
void fix(){
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
}
} rnk;
set<pii> st[4*mxN];
void update(int v,int l,int r,int ind,pii val,int t){
if(l>ind || r<ind) return;
if(t) st[v].insert(val);
else if(st[v].count(val)) st[v].erase(val);
if(l==r) return;
int m=(l+r)>>1;
update(v<<1,l,m,ind,val,t);
update(v<<1|1,m+1,r,ind,val,t);
}
pii query(int v,int l,int r,int lq,int rq,int lo,int hi){
// deb(l,r);
if(lq>rq) return {-1,-1};
if(l>=lq && r<=rq){
// deb(sz(st[v]),l,r,lq,rq,lo,hi);
if(!sz(st[v])) return {-1,-1};
if(st[v].rbegin()->first<lo) return {-1,-1};
if(st[v].begin()->first>hi) return {-1,-1};
return *st[v].lower_bound(pii(lo,hi));
}
int m=(l+r)>>1;
return max(query(v<<1,l,m,lq,min(rq,m),lo,hi),query(v<<1|1,m+1,r,max(lq,m+1),rq,lo,hi));
}
struct rect{
ll a,b,c,d,i;
};
struct paint{
int x,y,k;
};
vector<int> graph[mxN];
set<int> col[mxN];
int ans[mxN];
void dfs(int at){
for(int &i:graph[at]){
dfs(i);
if(sz(col[i])>sz(col[at])) swap(col[i],col[at]);
for(int j:col[i])
col[at].insert(j);
col[i].clear();
}
ans[at]=sz(col[at]);
}
map<pii,vector<int>> mp;
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,m; cin>>n>>m;
vector<rect> all,ori;
vector<paint> off;
for(int i=0;i<n;i++){
int a,b,c,d; cin>>a>>b>>c>>d;
rnk.add(a); rnk.add(c);
all.pb({a,b,c,d,i});
ori.pb({a,b,c,d,i});
}
for(int i=0;i<m;i++){
int x,y,k; cin>>x>>y>>k;
rnk.add(x);
off.pb({x,y,k});
}
rnk.fix();
sort(all.begin(),all.end(),[&](auto x,auto y){return (x.c-x.a)*(x.d-x.b)<(y.c-y.a)*(y.d-y.b);});
int N=sz(rnk.all);
// assert(sz(rnk.all)<mxN);
for(auto &[a,b,c,d,i]:all){
// deb(a,b,c,d,i);
a=rnk.get(a);
c=rnk.get(c);
pii res;
while(1){
res=query(1,1,N,a,c,b,d);
if(res==pii(-1,-1)) break;
// deb(res.first,res.second);
graph[min(i,(ll)res.second)].pb(max(i,(ll)res.second));
update(1,1,N,rnk.get(ori[res.second].a),res,0);
}
update(1,1,N,a,{b,i},1);
}
for(int i=1;i<=4*N;i++)
st[i].clear();
for(auto &[x,y,k]:off){
x=rnk.get(x);
update(1,1,N,x,{y,k},1);
mp[{y,k}].pb(x);
}
sort(all.begin(),all.end(),[&](auto x,auto y){return x.i>y.i;});
for(auto &[a,b,c,d,i]:all){
pii res;
// deb(a,b,c,d,i);
while(1){
res=query(1,1,N,a,c,b,d);
if(res==pii(-1,-1)) break;
// deb(res.first,res.second);
if(sz(mp[res])){
col[i].insert(res.second);
int x=mp[res].back();
mp[res].pop_back();
update(1,1,N,x,res,0);
} else break;
}
}
memset(ans,-1,sizeof(ans));
for(int i=0;i<n;i++){
if(ans[i]==-1) dfs(i);
cout<<ans[i]<<"\n";
}
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:124:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
124 | for(auto &[a,b,c,d,i]:all){
| ^
plahte.cpp:140:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
140 | for(auto &[x,y,k]:off){
| ^
plahte.cpp:146:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
146 | for(auto &[a,b,c,d,i]:all){
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
587 ms |
113732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
549 ms |
110540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
990 ms |
133464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1790 ms |
168500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1959 ms |
168652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
