Submission #1259441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259441		NoLove	Plahte (COCI17_plahte)	C++20	160 / 160	548 ms	237120 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;

int cur_value;
void upd(int v = 1, int l = 1, int r = si(nen)) {
    
    if (cur.y1 > r or l > cur.y2) return;
    if (cur.id == 174)
    db(v, st[v].back())
    if (!st[v].empty() && st[v].back().f > cha.f) cha = st[v].back();
    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].back().se == cur_value);
        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("./contest1_testdata/plahte/plahte.in.1a", "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;
        if (i == 3) db(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 + i, 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();
    };

// 174: (7435 716668642) (736777966 718695517)
//   3: (7416 716668623) (757243825 719274647)
// 1540: 7392 7238 757748639 722290487
// (nxt[3]) : ({ 3 174 581 1280 2274 2652 4412 4963 5261 6313
                //  6448 6492 7113 7160 7237 7840 7978 8014 8361 8693 
                //  9670 10322 11191 11864 11913 12473 13102 13230 13778 
                //  14939 15162 15783 16277 16566 17122 17207 18441 19329 }
// ) 
    db(id(107869543), id(764565751))
//
//
    // db(nen)
    sort(all(events));
    int timer = 0;
    for (auto[x, type, y1, y2] : events) {
        // if (type == -3 or type == -1540 or type - INF == 3 or type - INF == 1540)
        // db(x, type, y1, y2, "goc")
        x = id(x); y1 = id(y1); y2 = id(y2);
        // if (type == -3 or type == -1540 or type - INF == 3 or type - INF == 1540)
        // db(type, x, y1, y2)
        ++timer;
        if (type < 0) {
            cur = {y1, y2, -type, timer}; cha = {-1, 0};
            upd();
            if (cha.f != -1) {
                nxt[cha.se].push_back(-type);
            }
            if (-type == 174)
            db(-type, cha)
        } else if (type >= INF) {
            cur_value = 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) {
        // db(v, nxt[v])
        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:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen("hi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:78:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |        freopen("hi.out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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