#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
void IOS(){
cin.tie(0) -> sync_with_stdio(0);
#ifndef ONLINE_JUDGE
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#else
#define er(args ...) 0
#endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
int n, seg[maxn], par[maxn], ans[maxn];
set<int> cl[maxn];
void shift(int x){
if(seg[x]+1){
seg[x<<1] = seg[x<<1|1] = seg[x];
}
}
void upd(int l, int r, int k, int x = 1, int lx = 0, int rx = n){
if(l <= lx && r >= rx){
seg[x] = k;
return;
}
shift(x);
int mid = (lx + rx)>>1;
if(l < mid) upd(l, r, k, x<<1, lx, mid);
if(mid < r) upd(l, r, k, x<<1|1, mid, rx);
seg[x] = seg[x<<1] == seg[x<<1|1]? seg[x<<1]: -1;
}
int get(int i, int x = 1, int lx = 0, int rx = n){
if(seg[x] + 1) return seg[x];
int mid = (lx + rx)>>1;
if(i < mid) return get(i, x<<1, lx, mid);
return get(i, x<<1|1, mid, rx);
}
int main(){ IOS();
int n, m; cin >> n >> m;
vector<pair<pp, pp>> rec;
vector<pair<pp, int>> pnt;
map<int, int> cmpX, cmpY;
rep(i,0,n){
int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
rec.pb({{x1, y1}, {x2, y2}});
cmpX[x1] = cmpX[x2] = cmpY[y1] = cmpY[y2] = 0;
}
rep(i,0,m){
int x, y, k; cin >> x >> y >> k;
cmpX[x] = cmpY[y] = 0;
pnt.pb({{x, y}, k});
}
int id = 0;
for(auto&c: cmpX) c.ss = id++;
id = 0;
for(auto&c: cmpY) c.ss = id++;
::n = id;
rep(i,0,n) rec[i].ff.ff = cmpX[rec[i].ff.ff], rec[i].ff.ss = cmpY[rec[i].ff.ss],
rec[i].ss.ff = cmpX[rec[i].ss.ff], rec[i].ss.ss = cmpY[rec[i].ss.ss];
rep(i,0,m) pnt[i].ff.ff = cmpX[pnt[i].ff.ff], pnt[i].ff.ss = cmpY[pnt[i].ff.ss];
struct Event{
int l, r, id;
bool is_add;
};
vector<vector<Event>> st(sz(cmpX)+1);
rep(i,0,n){
st[rec[i].ff.ff].pb({rec[i].ff.ss, rec[i].ss.ss, i+1, true});
st[rec[i].ss.ff+1].pb({rec[i].ff.ss, rec[i].ss.ss, i+1, false});
}
rep(i,0,m){
auto[x, y] = pnt[i].ff;
st[x].pb({y, pnt[i].ss, -1, false});
}
rep(i,0,::n+1){
for(auto[l, r, id, is]: st[i]){
// er(i, l, r, id, is);
if(id > 0){
if(is){
par[id] = get(l);
upd(l, r+1, id);
// er(par[id]);
}
else{
upd(l, r+1, par[id]);
ans[id] = sz(cl[id]);
if(sz(cl[id]) > sz(cl[par[id]])) cl[id].swap(cl[par[id]]);
for(int c: cl[id]) cl[par[id]].insert(c);
cl[id].clear();
}
}else{
cl[get(l)].insert(r);
// er(get(l));
}
}
}
rep(i,1,n+1) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
147 ms |
34208 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
172 ms |
39600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
316 ms |
59304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
632 ms |
87800 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
592 ms |
88564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
