Submission #1208623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208623		urejgi	Plahte (COCI17_plahte)	C++17	0 / 160	309 ms	51064 KiB

plahte

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

typedef long long ll;

constexpr ll N = 1e5;

struct pt{
    ll x,y;
    pt(const ll&x_ = 0, const ll&y_ = 0) : x(x_), y(y_) {}
    bool operator<(const pt&p)const{
        return x < p.x || (x == p.x && y < p.y); 
    }
};

struct Line{
    ll x1, y1, x2, y2, i;
    Line(const ll&x1_ = 0, const ll&y1_ = 0, const ll&x2_ = 0, 
        const ll&y2_ = 0, const ll&i_ = 0) : x1(x1_), y1(y1_), x2(x2_), y2(y2_), i(i_) {}
};

struct ST{
    ll inf = N-1;
    int n;
    vector<ll> lz;
    ST(int n_){
        n = n_;
        lz.assign(n<<2|1, 0);
        lz[1] = inf;
    }
    void push(int t, int l, int r){
        if(lz[t] == -1) return;
        if(l != r){
            lz[t<<1] = lz[t];
            lz[t<<1|1] = lz[t];
            lz[t] = -1;
        }
    }
    void upd(int t, int l, int r, int ql, int qr, int x){
        push(t, l, r);
        if(l > r || l > qr || ql > qr || ql > r) return;
        if(ql <= l && r <= qr){
            lz[t] = x;
            return;
        }
        int m = (l+r)>>1;
        upd(t<<1,l,m,ql,qr,x);
        upd(t<<1|1,m+1,r,ql,qr,x);
    }
    void upd(int l, int r, int x){
        upd(1,1,n,l,r,x);
    }
    int get(int t, int l, int r, int i){
        if(l == r) return lz[t];
        push(t,l,r);
        int m = (l+r)>>1;
        if(i <= m) return get(t<<1,l,m,i);
        else return get(t<<1|1,m+1,r,i);
    }
    int get(int i){
        return get(1, 1, n, i);
    }
};

ST tree(N*3);

ll n,m;
vector<Line> a;
vector<set<ll>> col(N);
vector<ll> ind(N), pr(N, N-1), ans(N, -1);
vector<pair<pair<ll, ll>, ll>> P;
vector<ll> g[N];
map<ll, ll> mp;


void merge(ll x, ll y){
    if(col[ind[x]].size() > col[ind[y]].size()) swap(ind[x], ind[y]);
    for(ll x:col[ind[x]]) col[ind[y]].insert(x);
}

void sweep(){
    set<pair<ll, ll>> s;
    pair<ll, ll> p, pos;
    ll ptr, par = 0, f = 0, last = 0;
    for(auto[p,ptr]:P){
        par = tree.get(mp[p.second]);
        if(f){
            f = 0;
            if(pos == p){
                col[ind[ptr]].insert(last);
            }
        }
        if(ptr < 0){
            if(par != N-1) col[ind[par]].insert(ptr);
            pos = p;
            last = ptr;
            f = 1;
        }else if(s.find(make_pair(a[ptr].x1, a[ptr].y1)) == s.end()){
            s.insert(p);
            g[ptr].push_back(par);
            g[par].push_back(ptr);
            tree.upd(mp[a[ptr].y1], mp[a[ptr].y1], ptr);
            pr[ptr] = par;
        }else{
            s.erase(make_pair(a[ptr].x1, a[ptr].y1));
            tree.upd(mp[a[ptr].y1], mp[a[ptr].y2], pr[ptr]);
        }
    }
}

void dfs(ll v, ll pv){
    for(ll u:g[v]){
        if(u == pv) continue;
        dfs(u,v);
        if(v != N-1) merge(u,v);
    }
    if(v != N-1) ans[v] = col[ind[v]].size();
}

void solve(){
    ll x,y,v,z;
    cin >> n >> m;
    vector<ll> ys;
    for(ll i = 0; i < n; i++){
        cin >> x >> y >> v >> z;
        a.push_back(Line(x,y,v,z,i));
        P.push_back({{x,y},i});
        P.push_back({{v,z},i});
        ys.push_back(y);
        ys.push_back(z);
        ind[i] = i;
    }
    for(ll i = 0; i < m; i++){
        cin >> x >> y >> v;
        ys.push_back(y);
        P.push_back({{x,y},-v});
    }
    sort(P.begin(), P.end());
    sort(ys.begin(), ys.end());
    for(ll i = 0; i < (ll)ys.size(); i++) mp[ys[i]] = i+1;
    sweep();
    dfs(N-1, -1);
    for(ll i = 0; i < n; i++) cout << ans[i] << '\n';
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    solve();
    return 0;
}

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