Submission #667796

#	Time	Username	Problem	Language	Result	Execution time	Memory
667796		slo	Plahte (COCI17_plahte)	C++17	0 / 160	1535 ms	524288 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define Pi acos(-1.0)
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sz(a) (a.size())
#define all(a) a.begin(), a.end()
#define numZeroBitStart(x) (__builtin_clz(x))
#define numZeroBitEnd(x) (__builtin_ctz(x))
#define numOneBit(x) (__builtin_popcount(x))
#define parityOfNumOneBit(x) (__builtin_parity(x))

typedef long long ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
typedef pair<ll,int> plli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps=1e-9;
        if(x+eps<y){
            x=y; return true;
        }
        return false;
    }

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps=1e-9;
        if(x>y+eps){
            x=y; return true;
        }
        return false;
    }

/*-----------------MAIN PROGRAM-----------------*/

struct Point{ ll x, y; int recId;};
struct Rec{ Point p, q; int id;};
struct Shot{ ll x, y; int color;};

struct SegTree{
    int n;
    vector<set<pii>> seg, lazy;
    SegTree(int _n=0){
        n=_n;
        seg.assign(4*n+7,set<pii>());
        lazy.assign(4*n+7,set<pii>());
    }
    void down(int i, int l, int r){
        if(l<r){
            for(pii cmd:lazy[i]){
                int k=i<<1;

                auto it=seg[k].find(cmd);
                if(it==seg[k].end()) seg[k].ins(cmd);
                else seg[k].erase(it);

                it=seg[k+1].find(cmd);
                if(it==seg[k+1].end()) seg[k+1].ins(cmd);
                else seg[k+1].erase(it);

                it=lazy[k].find(cmd);
                if(it==lazy[k].end()) lazy[k].ins(cmd);
                else lazy[k].erase(it);

                it=lazy[k+1].find(cmd);
                if(it==lazy[k+1].end()) lazy[k+1].ins(cmd);
                else lazy[k+1].erase(it);
            }
            lazy[i].clear();
        }
    }
    void upd(int i, int l, int r, int u, int v, pii cmd){
        if(v<l || r<u) return;
        if(u<=l && r<=v){
            auto it=seg[i].find(cmd);
            if(it==seg[i].end()) seg[i].ins(cmd);
            else seg[i].erase(it);

            it=lazy[i].find(cmd);
            if(it==lazy[i].end()) lazy[i].ins(cmd);
            else lazy[i].erase(it);
            return;
        }
        down(i,l,r);
        int m=(l+r)>>1, k=i<<1;
        upd(k,l,m,u,v,cmd);
        upd(k+1,m+1,r,u,v,cmd);
    }
    void upd(int u, int v, pii cmd){
        upd(1,0,n,u,v,cmd);
    }
    int calc(int i, int l, int r, int pos){
        if(pos<l || r<pos) return -1;
        down(i,l,r);
        if(l==r){
            if(seg[i].empty()) return -1;
            return seg[i].rbegin()->se;
        }
        int m=(l+r)>>1, k=i<<1;
        return max(calc(k,l,m,pos),calc(k+1,m+1,r,pos));
    }
    int calc(int pos){
        return calc(1,0,n,pos);
    }
};

const int N=1e5+7;

int n, m;
vector<Rec> rec;
vector<Point> P;

vi adj[N];
set<int> unqCol[N];
int timer;
int t[N], par[N];

vi yVal;

bool operator ==(const Point& p, const Point& q){
    return mp(p.x,p.y)==mp(q.x,q.y);
}

bool operator <(const Point& p, const Point& q){
    if(p.x==q.x){
        if(p.recId<0 && q.recId<0)
            return p.y<q.y;
        if(p.recId<0)
            return q==rec[q.recId].q;
        if(q.recId<0)
            return p==rec[p.recId].p;
        return p.y<q.y;
    }
    return p.x<q.x;
}

int getId(const int& y){
    return lower_bound(all(yVal),y)-yVal.begin();
}

void makeTree(){
    sort(all(P));
    sort(all(yVal));
    yVal.resize(unique(all(yVal))-yVal.begin());

    rep(i,n) par[i]=i;

    timer=0;
    set<Point> active;
    SegTree st(sz(yVal));
//    st.upd(getId(rec[0].p.y),getId(rec[0].q.y),mp(0,0));
//    cout<<st.calc(getId(3));
    for(Point p:P)
        if(p.recId<0){
            int tmp=st.calc(getId(p.y));
            if(tmp!=-1)
                unqCol[tmp].ins(-p.recId);
        }
        else{
            auto it=active.find(rec[p.recId].p);
            if(it==active.end()){ // add
                t[p.recId]=timer++;
                st.upd(getId(rec[p.recId].p.y),getId(rec[p.recId].q.y),mp(t[p.recId],p.recId));
                auto pos=active.ins(p).fi;
                if(pos!=active.begin()){
                    pos--;
                    adj[pos->recId].pb(p.recId);
                    par[p.recId]=(pos->recId);
                }
            }
            else{ // remove
                st.upd(getId(rec[p.recId].p.y),getId(rec[p.recId].q.y),mp(t[p.recId],p.recId));
                active.erase(it);
            }
        }
}

void dfs(int u){
    int mxV=-1;
    for(int v:adj[u]){
        dfs(v);
        if(mxV==-1 || sz(unqCol[mxV])<sz(unqCol[v])) mxV=v;
    }

    if(mxV!=-1){
        set<int> cur=unqCol[mxV];
        for(int c:unqCol[u]) cur.ins(c);
        for(int v:adj[u]) if(v!=mxV)
            for(int c:unqCol[v]) cur.ins(c);
        unqCol[u]=cur;
    }
}

void read(){
    cin>>n>>m;
    rep(i,n){
        Rec r;
        cin>>r.p.x>>r.p.y>>r.q.x>>r.q.y;
        r.id=r.p.recId=r.q.recId=i;
        rec.pb(r), P.pb(r.p), P.pb(r.q);
        yVal.pb(r.p.y), yVal.pb(r.q.y);
    }
    rep(i,m){
        Point p; cin>>p.x>>p.y>>p.recId;
        p.recId=-p.recId;
        P.pb(p), yVal.pb(p.y);
    }
}

void solve(){
    makeTree();
    rep(i,n) if(par[i]==i) dfs(i);
    rep(i,n) cout<<sz(unqCol[i])<<'\n';
}

int main(){
    fastIO;
    read();
    solve();
    return 0;
}

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