Submission #638825

#	Time	Username	Problem	Language	Result	Execution time	Memory
638825		inksamurai	Plahte (COCI17_plahte)	C++17	0 / 160	187 ms	21960 KiB

plahte

#include <bits/stdc++.h>


// cut here
#ifdef _MSC_VER
#include <intrin.h>
#endif
 
namespace atcoder {
 
namespace internal {
 
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
 
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}
 
}  // namespace internal
 
}  // namespace atcoder
 
 
namespace atcoder {
 
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
 
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
 
    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }
 
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
 
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
 
    S all_prod() { return d[1]; }
 
    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
 
    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
 
  private:
    int _n, size, log;
    std::vector<S> d;
 
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
 
}  // namespace atcoder
// cut here 


using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3RhsN1z ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

// struct Q{
// 	int t,y,id;
// 	Q(int _t=0,int _y=0,int _id=0):
// 	t(_t),y(_y),id(_id){}
// };

const int inf=1e9;
pii op(pii l,pii r){return l.fi>r.fi?l:r;}
pii e(){return {-inf,-1};}

signed main(){
_3RhsN1z;
	int n,q;
	cin>>n>>q;
	
	using Fp=pair<pii,pii>;
	vec(Fp) a;
	rep(i,n){
		pii s,t;
		cin>>s.fi>>s.se>>t.fi>>t.se;
		a.pb(Fp(s,t));
	}
	
	vec(Fp) qry;
	rep(_,q){
		int x,y,k;
		cin>>x>>y>>k;
		qry.pb(Fp(pii(x,y),pii(k,_)));
	}
	
	#define uniq(tmp) sort(tmp.begin(),tmp.end()),tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end())
	{
		vi tmp;
		rep(i,n){
			tmp.pb(a[i].fi.fi);
			tmp.pb(a[i].se.fi);
			tmp.pb(a[i].fi.se);
			tmp.pb(a[i].se.se);
		}
		rep(i,q){
			tmp.pb(qry[i].fi.fi);
			tmp.pb(qry[i].fi.se);
		}
		uniq(tmp);
		rep(i,n){
			pii s=a[i].fi,t=a[i].se;
			s.fi=(int)(lower_bound(tmp.begin(),tmp.end(),s.fi)-tmp.begin());
			s.se=(int)(lower_bound(tmp.begin(),tmp.end(),s.se)-tmp.begin());
			t.fi=(int)(lower_bound(tmp.begin(),tmp.end(),t.fi)-tmp.begin());
			t.se=(int)(lower_bound(tmp.begin(),tmp.end(),t.se)-tmp.begin());
			a[i].fi=s;
			a[i].se=t;
		}
		rep(i,q){
			pii s=qry[i].fi;
			s.fi=(int)(lower_bound(tmp.begin(),tmp.end(),s.fi)-tmp.begin());
			s.se=(int)(lower_bound(tmp.begin(),tmp.end(),s.se)-tmp.begin());
			qry[i].fi=s;
		}
	}

	const int m=2*n+q;
	vec(vec(pii)) adqry(m);
	rep(i,n){
		pii s,t;
		s=a[i].fi,t=a[i].se;
		adqry[s.fi].pb({0,i});
		adqry[t.fi+1].pb({1,i});
	}
	rep(i,q){
		pii s=qry[i].fi;
		adqry[s.fi].pb({2,i});
	}

	atcoder::segtree<pii,op,e> seg(m);
	vec(vi) adj(n),qs(n);
	vi deg(n);
	rep(i,m){
		for(auto [t,id]:adqry[i]){
			if(t==0){
				int sy=a[id].fi.se;
				int ty=a[id].se.se;
				seg.set(sy,{ty,id});
				//find first to the left of sy 
				int _l=0,_r=sy-1;
				int _c=-1;
				while(_l<=_r){
					int _m=(_l+_r)/2;
					if(seg.prod(_m,sy).fi>=ty){
						_c=_m,_l=_m+1;
					}else{
						_r=_m-1;
					}
				}
				if(_c!=-1){
					int u=seg.get(_c).se;
					adj[u].pb(id);
					deg[id]+=1;
				}
			}else if(t==1){
				int sy=a[id].fi.se;
				seg.set(sy,{-inf,-1});
			}else{
				int sy=qry[id].fi.se;
				//find first from the left 
				int _l=0,_r=sy;
				int _c=-1;
				while(_l<=_r){
					int _m=(_l+_r)/2;
					if(seg.prod(_m,sy+1).fi>=sy){
						_c=_m,_l=_m+1;
					}else{
						_r=_m-1;
					}
				}
				if(_c!=-1){
					int u=seg.get(_c).se;
					qs[u].pb(qry[id].se.fi);
				}
			}
		}
	}

	vi rts;
	rep(v,n){
		if(deg[v]==0){
			rts.pb(v);
		}
	}

	vi ctr(n);
	vec(set<int>) rbts(n);
	vi pns(n);
	auto dfs=[&](auto self,int v,int par)->void{
		ctr[v]=v;
		for(auto k:qs[v]){
			rbts[v].insert(k);
		}
		int opt=v;
		for(auto u:adj[v]){
			self(self,u,v);
			int up=ctr[u];
			if(sz(rbts[up])>sz(rbts[opt])){
				opt=up;
			}
		}
		for(auto u:adj[v]){
			int up=ctr[u];
			if(up!=opt){
				for(auto x:rbts[up]){
					rbts[opt].insert(x);
				}
			}
		}
		ctr[v]=opt;
		for(auto k:qs[v]){
			rbts[opt].insert(k);
		}
		pns[v]=sz(rbts[opt]);
	};
	for(auto rt:rts){
		dfs(dfs,rt,-1);
	}
	rep(v,n){
		cout<<pns[v]<<"\n";
	}
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32