oj.uz

Submission #735191

# Submission time Handle Problem Language Result Execution time Memory
735191 2023-05-03T16:50:45 Z vjudge1 Plahte (COCI17_plahte) C++17
0 / 160
 2000 ms 52668 KB 
// no buresu
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

#define fileio(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

const int maxn = 80004;

struct node {
    int val = 0, lazy = 0;
} st[maxn*16];

void pushdown(int id) {
    int x = st[id].lazy;
    st[id].lazy = 0;

    st[id*2].val += x;
    st[id*2].lazy += x;

    st[id*2+1].val += x;
    st[id*2+1].lazy += x;
}

void update(int id, int l, int r, int a, int b, int v) {
    if (r < a || b < l) return;
    if (a <= l && r <= b) {
        st[id].val += v;
        st[id].lazy += v;
        return;
    }
    pushdown(id);

    int mid = (l+r)>>1;
    update(id*2, l, mid, a, b, v);
    update(id*2+1, mid+1, r, a, b, v);

    st[id].val = max(st[id*2].val, st[id*2+1].val);
}

int get(int id, int l, int r, int i) {
    if (l == r) return st[id].val;
    pushdown(id);

    int mid = (l+r)>>1;
    if (i <= mid) {
        return get(id*2, l, mid, i);
    } else {
        return get(id*2+1, mid+1, r, i);
    }
}

int n, m;
vector<int> ax, ay;

void mmb(int &x, vector<int> &a) {
    x = lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
}

struct Rect {
    int x1, y1, x2, y2;

    void Compress() {
        mmb(x1, ax); mmb(x2, ax);
        mmb(y1, ay); mmb(y2, ay);
    }
} a[maxn];

struct Point {
    int x, y, c;

    void Compress() {
        mmb(x, ax);
        mmb(y, ay);
    }
} b[maxn];

vector<pair<int, int>> pts[maxn*4]; // <idx, open/close>
vector<int> adj[maxn], pts2[maxn*4], L[maxn];
int res[maxn];

void MakeEdge(int x, int y) {
    adj[x].push_back(y);
    adj[y].push_back(x);
}

vector<int> roots;
void dfs(int u, int p = 0) {
    for (int v: adj[u]) {
        if (v != p) {
            dfs(v, u);

            if (L[u].size() < L[v].size()) swap(L[u], L[v]);
            for (int c: L[v]) {
                L[u].push_back(c);
            }
            L[v].clear();
        }
    }
    sort(L[u].begin(), L[u].end());
    L[u].erase(unique(L[u].begin(), L[u].end()), L[u].end());

    res[u] = L[u].size();
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fileio("paint");

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
        ax.push_back(a[i].x1);
        ax.push_back(a[i].x2);
        ay.push_back(a[i].y1);
        ay.push_back(a[i].y2);
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i].x >> b[i].y >> b[i].c;
        ax.push_back(b[i].x);
        ay.push_back(b[i].y);
    }

    sort(ax.begin(), ax.end());
    sort(ay.begin(), ay.end());

    for (int i = 1; i <= n; i++) {
        a[i].Compress();
        pts[a[i].x1].push_back({i, 1});
        pts[a[i].x2].push_back({i, 0});
    }
    for (int i = 1; i <= m; i++) {
        b[i].Compress();
        pts2[b[i].x].push_back(i);
    }

    // 1st sweepline
    map<int, int> f; // maps number in segment tree to index of rectangle
    for (int i = 1; i <= n*4; i++) {
        for (auto z: pts[i]) {
            int idx = z.first;
            if (z.second) {
                int par = get(1, 1, n*4, a[idx].y1);
                if (par > 0) {
                    MakeEdge(idx, f[par]);
                } else {
                    roots.push_back(idx);
                }

                update(1, 1, n*4, a[idx].y1, a[idx].y2, 1);
                f[par+1] = idx;
            } else {
                f.erase(get(1, 1, n*4, a[idx].y1));
                update(1, 1, n*4, a[idx].y1, a[idx].y2, -1);
            }
        }

        for (int idx: pts2[i]) {
            int id = f[get(1, 1, n*4, b[idx].y)];
            L[id].push_back(b[idx].c);
        }
    }

    for (int u: roots) {
        dfs(u);
    }
    for (int i = 1; i <= n; i++) {
        cout << res[i] << "\n";
    }

    return 0 ^ 0;
}

Compilation message

plahte.cpp: In function 'int32_t main()':
plahte.cpp:7:59: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define fileio(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:110:5: note: in expansion of macro 'fileio'
  110 |     fileio("paint");
      |     ^~~~~~
plahte.cpp:7:92: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define fileio(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:110:5: note: in expansion of macro 'fileio'
  110 |     fileio("paint");
      |     ^~~~~~

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 27500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2049 ms 30024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2061 ms 39212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 52668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 50064 KB Time limit exceeded
2 Halted 0 ms 0 KB -