Submission #1259418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259418		NoLove	Plahte (COCI17_plahte)	C++20	0 / 160	417 ms	215772 KiB

plahte

/**
 *    author : Lăng Trọng Đạt
 *    created: 2025-08-16
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
//#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int i = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;

const int N = 1e6 + 5;
int g[N];
int n, m, k, a, b, c, d;
vector<int> nen = {-1}, nxt[N];
set<int> cover[N];

vector<vector<pii>> st;
struct Info {
    int y1, y2, id, t;
} cur;
pii cha;

void upd(int v = 1, int l = 1, int r = si(nen)) {
//    db(v, st[v])
    if (!st[v].empty() && st[v].back().f > cha.f) cha = st[v].back();

    if (cur.y1 > r or l > cur.y2) return;
    else if (cur.y1 <= l && r <= cur.y2) {
        st[v].push_back({cur.t, cur.id});
    } else {
        int mid = (l + r) / 2;
        upd(2*v, l, mid); upd(2*v + 1, mid + 1, r);
    }
}
void pop_st(int y1, int y2, int v = 1, int l = 1, int r = si(nen)) {
    if (y1 > r or l > y2) return;
    else if (y1 <= l && r <= y2) {
        assert(!st[v].empty());
        st[v].pop_back();
    } else {
        int mid = (l + r) / 2;
        pop_st(y1, y2, 2*v, l, mid); pop_st(y1, y2, 2*v + 1, mid + 1, r);
    }
}
pii get(int y, int v = 1, int l = 1, int r = si(nen)) {
    if (l > y or y > r) return {-1, -1};
    if (l == r) {
        return st[v].back();
    } else {
        int mid = (l + r) / 2;
        return max({st[v].back(),
                    get(y, 2*v, l, mid),
                    get(y, 2*v + 1, mid + 1, r)});
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("hi.inp", "r")) {
        freopen("hi.inp", "r", stdin);
//        freopen("hi.out", "w", stdout);
    }

    cin >> n >> m;
    vector<array<int, 4>> events; // {x, type, y1, y2}
    // type = -1: open rect, 0: point, INF: close rect
    vector<pii> ord; // {dien tich, id}
    FOR(i, 1, n) {
        cin >> a >> b >> c >> d;
        nen.pb(a); nen.pb(b); nen.pb(c); nen.pb(d);
        events.push_back({a, -i, b, d}); // i just care about id when open it
        events.push_back({c, INF, b, d});
        ord.push_back({(c - a) * (d - b), i});
    }
    FOR(i, 1, m) {
        cin >> a >> b >> k;
        events.push_back({a, k, b, b});
        nen.pb(a); nen.pb(b);
    }

    sort(all(nen));
    nen.resize(unique(all(nen)) - nen.begin());
    st = vector<vector<pii>>(5*si(nen), {{-1, -1}});
    auto id = [&](int x) -> int {
        return lower_bound(all(nen), x) - nen.begin();
    };
//
//
    sort(all(events));
    int timer = 0;
    for (auto[x, type, y1, y2] : events) {
        x = id(x); y1 = id(y1); y2 = id(y2);
        ++timer;
        if (type < 0) {
            cur = {y1, y2, -type, timer}; cha = {-1, 0};
            upd();
            if (cha.f != -1) {
                nxt[cha.se].push_back(-type);
            }
            db(-type, cha)
        } else if (type == INF) {
            pop_st(y1, y2);
        } else {
            pii cha = get(y1);
            if (cha.f != -1)
                cover[cha.se].insert(type);
            db(cha)
        }
    }

    sort(all(ord)); // làm theo các cạnh từ nhỏ -> lớn
    vector<int> ans(n + 1);
    for (auto[dien_tich, v] : ord) {
        for (int u : nxt[v]) {
            if (si(cover[u]) > si(cover[v])) swap(cover[u], cover[v]);
            for (int c : cover[u]) cover[v].insert(c);
        }

        ans[v] = si(cover[v]);
    }

    FOR(i, 1, n) {
        cout << ans[i] << "\n";
    }
}

Compilation message (stderr)

plahte.cpp: In function 'int32_t main()':
plahte.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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