Submission #1270484

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270484		ac_quan	Plahte (COCI17_plahte)	C++20	160 / 160	290 ms	102920 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define all(ac) ac.begin(),ac.end()
#define task "tet"
#define fi first
#define se second
#define db long double

struct segtree {
    int n;
    vector <vector<int> > trace;
    segtree(int n) {
        this -> n = n;
        trace.resize(4 * n + 1);
    }

    void update(int id, int l, int r, int u, int v, int w) {
        if(l > v || r < u) return;
        if(l >= u && r <= v) {
            if(w < 0) trace[id].pop_back();
            else trace[id].push_back(w);
            return;
        }

        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, w);
        update(id << 1 | 1, mid + 1, r, u, v, w);
        return;
    }

    int get(int id, int l, int r, int pos) {
        int res = 0;
        while(true) {
            int mid = (l + r) >> 1;
            if(trace[id].size() > 0) res = trace[id].back();
            if(l == r) break;
            if(mid >= pos) r = mid, id = id << 1;
            else l = mid + 1, id = id << 1 | 1;
        }
        return res;
    }
};

struct Event {
    int x, y1, y2, type;
    bool operator <(const Event o) {
        if(x != o.x) return x < o.x;
        return type > o.type;
    }
};

const int N = 6e5 + 1;
vector <int> g[N];
set <int> s[N];
int ans[N];

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

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n, m; cin >> n >> m;
    vector <int> rv;
    vector <Event> events;
    for(int i=1;i<=n;i++) {
        int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
        events.push_back({x1, y1, x2, y2});
        rv.emplace_back(x1);
        rv.emplace_back(x2);
        rv.emplace_back(y1);
        rv.emplace_back(y2);
    }

    for(int i=1;i<=m;i++) {
        int a, b, k; cin >> a >> b >> k;
        rv.emplace_back(a);
        rv.emplace_back(b);
        events.push_back({a, b, k, 0});
    }

    sort(all(rv));
    rv.erase(unique(all(rv)), rv.end());

    vector <Event> vt;
    for(int i=1;i<=n;i++) {
        auto e = events[i - 1];
        e.x = lower_bound(all(rv), e.x) - rv.begin() + 1;
        e.y1 = lower_bound(all(rv), e.y1) - rv.begin() + 1;
        e.y2 = lower_bound(all(rv), e.y2) - rv.begin() + 1;
        e.type = lower_bound(all(rv), e.type) - rv.begin() + 1;
        vt.push_back({e.x, e.y1, e.type, i});
        vt.push_back({e.y2, e.y1, e.type, -i});
    }

    for(int i=n+1;i<=n+m;i++) {
        auto e = events[i - 1];
        e.x = lower_bound(all(rv), e.x) - rv.begin() + 1;
        e.y1 = lower_bound(all(rv), e.y1) - rv.begin() + 1;
        vt.push_back({e.x, e.y1, e.y2, 0});
    }

    sort(all(vt));

    int sz = rv.size();
    segtree sg(sz);

    stack <int> stk;

    for(auto e:vt) {

        if(e.type < 0) sg.update(1, 1, sz, e.y1, e.y2, -1);
        else
        if(e.type == 0) {
            int pos = sg.get(1, 1, sz, e.y1);
            if(pos != 0) s[pos].insert(e.y2);
        }
        else {
            int pos = sg.get(1, 1, sz, e.y1);
            if(pos != 0) g[pos].push_back(e.type);
            else stk.emplace(e.type);

            sg.update(1, 1, sz, e.y1, e.y2, e.type);
        }
    }

    while(!stk.empty()) dfs(stk.top()), stk.pop();

    for(int i=1;i<=n;i++) cout << ans[i] << '\n';
    return 0;
}

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