Submission #1127136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127136		MinhKien	Plahte (COCI17_plahte)	C++17	0 / 160	2097 ms	45768 KiB

plahte

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

const int N = 1.6e5 + 1;

int n, m, ans[N], par[N];
std::set <int> s[N];
std::vector <int> v[N], Y;
std::vector < std::pair < std::pair <int, int>, int > > events;
bool IsRoot[N];

struct SegmentTree {
    int val[N << 2], lazy[N << 2];

    SegmentTree() {
        std::fill_n(val, N << 2, 0);
        std::fill_n(lazy, N << 2, -1);
    }

    void change (int id, int VAL) {
        val[id] = lazy[id] = VAL;
    }

    void down(int id) {
        if (lazy[id] == -1) return;

        change(id << 1, lazy[id]);
        change(id << 1 | 1, lazy[id]);
        lazy[id] = -1;
    }

    void update(int l, int r, int A, int B, int VAL, int id) {
        if (l > B || r < A) return;

        if (l >= A && r <= B) {
            change(id, VAL);
            return;
        }

        int mid = (l + r) >> 1;
        down(id);
        update(l, mid, A, B, VAL, id << 1);
        update(mid + 1, r, A, B, VAL, id << 1 | 1);

        val[id] = std::max(val[id << 1], val[id << 1 | 1]);
    }

    int get(int l, int r, int A, int B, int id) {
        if (l > B || r < A) return -1;

        if (l >= A && r <= B) return val[id];

        int mid = (l + r) >> 1;
        down(id);
        return std::max(get(l, mid, A, B, id << 1), get(mid + 1, r, A, B, id << 1 | 1));
    }
} seg;

struct rect {
    int x1, y1, x2, y2;
    int id, k;

    void input(int i) {
        if (i <= n) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            k = -1;
        } else {
            scanf("%d%d%d", &x1, &y1, &k);
            x2 = x1;
            y2 = y1;
        }

        Y.push_back(y1);
        Y.push_back(y2);

        id = i;
    }

    void output() {
        printf("%d %d %d %d\n", x1, y1, x2, y2);
    }

    bool in (int l, int r, int u) {
        return u >= l && u <= r;
    }

    bool rect_in (rect o) {
        return in(x1, x2, o.x1) && in(x1, x2, o.x2) && in(y1, y2, o.y1) && in(y1, y2, o.y2);
    }
} a[N];

bool cmp (rect x, rect y) {
    if (std::pair <int, int>(x.x1, x.y1) == std::pair <int, int>(y.x1, y.y1)) return std::pair <int, int>(x.x2, x.y2) < std::pair <int, int>(y.x2, y.y2);
    return std::pair <int, int>(x.x1, x.y1) < std::pair <int, int>(y.x1, y.y1);
}

std::unordered_map <int, int> ID;
int GetID(int p) {
    return ID[p];
}

void DFS(int u) {
    if (a[u].k != -1) {
        s[u].insert(a[u].k);
    }

    for (int z: v[u]) {
        DFS(z);
        if (s[u].size() > s[z].size()) s[u].swap(s[z]);
        for (int j: s[z]) s[u].insert(j);
        s[z].clear();
    }

    ans[a[u].id] = s[u].size();
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n + m; ++i) {
        a[i].input(i);
        IsRoot[i] = true;
    }

    sort(Y.begin(), Y.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());
    
    for (int i = 0; i < Y.size(); ++i) {
        ID[Y[i]] = i + 1;
    }

    std::sort(a + 1, a + n + m + 1, cmp);

    for (int i = 1; i <= n + m; ++i) {
        events.push_back(std::pair < std::pair <int, int>, int >(std::pair <int, int>(a[i].x1, a[i].y1), i));
        events.push_back(std::pair < std::pair <int, int>, int >(std::pair <int, int>(a[i].x2, a[i].y2), -i));
    }
    std::sort(events.begin(), events.end());

    int j = 0;
    for (int i = 1; i <= n + m; ++i) {
        while (j < events.size() && events[j].first < std::pair <int, int>(a[i].x1, a[i].y1)) {
            int cur = abs(events[j].second);
            if (events[j].second > 0) {
                seg.update(1, Y.size(), GetID(a[cur].y1), GetID(a[cur].y2), cur, 1);
            } else {
                int ph = par[cur];
                if (ph != 0) seg.update(1, Y.size(), GetID(a[ph].y1), GetID(a[ph].y2), ph, 1);
                else seg.update(1, Y.size(), GetID(a[cur].y1), GetID(a[cur].y2), 0, 1);
            }
            ++j;
        }

        int k = seg.get(1, Y.size(), GetID(a[i].y1), GetID(a[i].y2), 1);
        
        if (k > 0) {
            par[i] = k;
            v[k].push_back(i);
            IsRoot[i] = false;
        }
    }

    for (int i = 1; i <= n + m; ++i) {
        if (IsRoot[i]) {
            DFS(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        printf("%d\n", ans[i]);
    }

    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp: In member function 'void rect::input(int)':
plahte.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             scanf("%d%d%d", &x1, &y1, &k);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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