Submission #1124783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124783		luvna	Plahte (COCI17_plahte)	C++20	160 / 160	340 ms	104436 KiB

plahte

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 5e5 + 15;

struct rect{
    int x1, y1, x2, y2;
    rect() : x1(0), y1(0), x2(0), y2(0) {}
    rect(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

struct point{
    int x, y, col;
    point() : x(0), y(0), col(0) {}
    point(int x, int y, int col) : x(x), y(y), col(col) {}
};

int n, m;
pair<rect,int> a[N];
point b[N];
vector<int> compressX, compressY;
vector<pair<int,pii>> evt[N];
vector<pii> evtPoint[N];
set<int> s[N];
int par[N];
vector<int> g[N];
int InDeg[N], ans[N];

struct SegmentTree{
    int n;
    vector<int> st, lz;

    SegmentTree(int n) : n(n), st((n << 2) + 15, 0), lz((n << 2) + 15, -1) {}

    void change(int id, int val){
        lz[id] = st[id] = val;
    }

    void down(int l, int r, int id){
        if(lz[id] != -1){
            change(id<<1, lz[id]);
            change(id<<1|1, lz[id]);
            lz[id] = -1;
        }
    }

    void update(int l, int r, int id, int u, int v, int val){
        if(r < u || l > v) return;
        if(u <= l && r <= v){
            change(id, val);
            return;
        }
        int mid = (l+r) >> 1;
        down(l,r,id);
        update(l,mid,id<<1,u,v,val);
        update(mid+1,r,id<<1|1,u,v,val);
        st[id] = max(st[id<<1], st[id<<1|1]);
    }

    int get(int l, int r, int id, int u, int v){
        if(r < u || l > v) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = (l+r) >> 1;
        down(l,r,id);
        return max(get(l,mid,id<<1,u,v), get(mid+1,r,id<<1|1,u,v));
    }

    void update(int l, int r, int val){
        update(0,n,1,l,r,val);
    }

    int get(int l, int r){
        return get(0,n,1,l,r);
    }
};

void dfs(int u){
    for(int v : g[u]){
        dfs(v);
        if(sz(s[v]) > sz(s[u])) swap(s[u], s[v]);
        for(int x : s[v]) s[u].insert(x);
    }
    ans[u] = sz(s[u]);
}

void solve(){
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        int x, y, u, v; cin >> x >> y >> u >> v; u++;
        a[i] = {rect(x,y,u,v),i};
        compressX.push_back(x); compressX.push_back(u);
        compressY.push_back(y); compressY.push_back(v);
    }

    for(int i = 1; i <= m; i++){
        int x, y, col; cin >> x >> y >> col;
        b[i] = point(x,y,col);
        compressX.push_back(x);
        compressY.push_back(y);
    }

    sort(all(compressX)); sort(all(compressY));
    compact(compressX); compact(compressY);

    sort(a + 1, a + 1 + n, [&](auto a, auto b){
        return a.fi.x1 < b.fi.x1;
    });

    //for(int i = 0; i < sz(compressX); i++) cout << i << " " << compressX[i] << endl;

    for(int i = 1; i <= n; i++){
        auto e = a[i].fi;
        //cout << dbg(e.x1) << dbg(e.y1) << dbg(e.x2) << dbg(e.y2) << endl;
        e.x1 = lower_bound(all(compressX), e.x1) - compressX.begin();
        e.x2 = lower_bound(all(compressX), e.x2) - compressX.begin();
        e.y1 = lower_bound(all(compressY), e.y1) - compressY.begin();
        e.y2 = lower_bound(all(compressY), e.y2) - compressY.begin();
        //cout << dbg(e.x1) << dbg(e.y1) << dbg(e.x2) << dbg(e.y2) << endl;
        evt[e.x1].push_back({+i, pii(e.y1, e.y2)});
        evt[e.x2].push_back({-i, pii(e.y1, e.y2)});
        //cout << endl;
    }

    for(int i = 1; i <= m; i++){
        auto e = b[i];
        e.x = lower_bound(all(compressX), e.x) - compressX.begin();
        e.y = lower_bound(all(compressY), e.y) - compressY.begin();
        evtPoint[e.x].push_back(pii(e.y, e.col));
    }

    //sweep

    int maxN = sz(compressY);

    SegmentTree st(maxN);

    for(int i = 0; i < sz(compressX); i++){
        for(auto e : evt[i]){
            int id = e.fi;
            int l = e.se.fi, r = e.se.se;
            if(id > 0){
                int p = st.get(l,r);
                assert(p > -1);
                if(p){
                    g[a[p].se].push_back(a[id].se);
                    InDeg[a[id].se]++;
                    par[id] = p;
                }
                st.update(l,r,id);
            }
            else st.update(l,r,par[abs(id)]);
        }
        for(auto e : evtPoint[i]){
            int p = st.get(e.fi,e.fi);
            if(p) s[a[p].se].insert(e.se);
        }
    }

    //small to large

    for(int i = 1; i <= n; i++){
        if(!InDeg[i]) dfs(i);
    }

    for(int i = 1; i <= n; i++) cout << ans[i] << endl;
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:197:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:198:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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