Submission #1124393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124393		Mike_Vu	Plahte (COCI17_plahte)	C++17	160 / 160	341 ms	42236 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(x) (1LL << (x))
#define y1 LNTD

template<typename T> bool maximize(T& x, const T& y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T& x, const T& y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 2e5+5;
int n, m;

namespace full{
    struct SMT{
        int trsz;
        vector<int> tr, lazy;
        void init(int n) {
            trsz = 1;
            while (trsz < n) trsz <<= 1;
            tr.assign(trsz<<1, 0);
            lazy.assign(trsz<<1, -1);
        }
        void fix(int id) {
            if (lazy[id] == -1) return; ///0 means no
            if (id < trsz) {
                lazy[id<<1] = lazy[id];
                lazy[id<<1|1] = lazy[id];
            }
            tr[id] = lazy[id];
            lazy[id] = -1;
        }
        void update(int u, int v, int l, int r, int id, int val) {
            fix(id);
            if (l > v || r < u) return;
            if (l >= u && r <= v) {
                lazy[id] = val;
                fix(id);
                return;
            }
            int mid = (l+r)>>1;
            update(u, v, l, mid, id<<1, val);
            update(u, v, mid+1, r, id<<1|1, val);
        }
        void update(int u, int v, int val) {
            update(u, v, 1, trsz, 1, val);
        }
        int query(int u, int v, int l, int r, int id) {
            fix(id);
            if (l > v || r < u) return 0;
//            if ((l <= u && v <= r) && tr[id] > 0) return tr[id];
            if (l >= u && r <= v) {
                return tr[id];
            }
            int mid = (l+r)>>1;
            return max(query(u, v, l, mid, id<<1), query(u, v, mid+1, r, id<<1|1));
        }
        int query(int u, int v) {
            return query(u, v, 1, trsz, 1);
        }
    };
    struct event{
        int type, x, l, r, id;
        event(int _t, int _x, int _l, int _r, int _id) {
            type = _t;
            x = _x;
            l = _l;
            r = _r;
            id = _id;
        }
    };
    bool cmpe(event a, event b) {
        if (a.x != b.x) return a.x < b.x;
        return a.type > b.type;
    }
    vector<int> adj[maxn], roots, values;
    vector<event> e;
    int par[maxn], col[maxn], ans[maxn];
    set<int> st[maxn];
    SMT tr;
    int mp(int x) {
        return lower_bound(ALL(values), x)-values.begin()+1;
    }
    void sweepline() {
        sort(ALL(e), cmpe);
        tr.init((int)values.size());
        for (int i = 0; i < (int)e.size(); i++) {
            int l = mp(e[i].l), r = mp(e[i].r), id = e[i].id;
            if (e[i].type == 1) {
                //new
                //take par
                int p = tr.query(l, r);
                if (p == 0) {
                    roots.pb(id);
                }
                else {
                    adj[p].pb(id);
                }
                par[id] = p;
                //update
                tr.update(l, r, id);
            }
            else if (e[i].type == -1) {
                //end
                //reupdate par
                tr.update(l, r, par[id]);
            }
            else {
                //col
                //check par?
                //take par
                int p = tr.query(l, r);
                if (p == 0) continue;
                adj[p].pb(id);
                par[id] = p;
            }
        }
    }
    void dfs(int u) {
        for (int v : adj[u]) {
//            cout << u << ' ' << v << "\n";
            dfs(v);
            //merge
            if (st[u].size() < st[v].size()) swap(st[u], st[v]);
            for (int x : st[v]) st[u].insert(x);
        }
        if (col[u] > 0) st[u].insert(col[u]);
        ans[u] = st[u].size();
    }
    void solve() {
        //input
        for (int i = 1; i <= n ;i++) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            e.pb(event(1, x1, y1, y2, i));
            e.pb(event(-1, x2, y1, y2, i));
            values.pb(y1);
            values.pb(y2);
            col[i] = 0;
        }
        //i+n
        //set colors
        for (int i= n+1; i <= n+m; i++) {
            int x, y;
            cin >> x >> y >> col[i];
            e.pb(event(0, x, y, y, i));
            values.pb(y);
        }
        //discretize
        sort(ALL(values));
        values.erase(unique(ALL(values)), values.end());
        //build tree (multi-root) by sweepline
        sweepline();
        //small to large -> ans
        for (int u : roots) {
            dfs(u);
        }
        //output
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #define name "LOANGMUC"
    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    cin >> n >> m;
    return full::solve(), 0;
}
/*
3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 2
2 6 2
4 7 3
*/

Compilation message (stderr)

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

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