oj.uz

Submission #84425

# Submission time Handle Problem Language Result Execution time Memory
84425 2018-11-15T07:31:28 Z polyfish Plahte (COCI17_plahte) C++14
96 / 160
 2000 ms 88600 KB 
#include <bits/stdc++.h>
using namespace std;

#define y1 _y1_
#define y2 _y2_

const int MAX_N = 200002;
const int INF = 1e9;

struct rectangle {
    int x1, y1, x2, y2, c, id;

    rectangle() {}

    rectangle(int x1, int y1, int x2, int y2, int c, int id):
        x1(x1), y1(y1), x2(x2), y2(y2), c(c), id(id) {}

    bool operator < (const rectangle &R) const {
        if (x2 != R.x2)
            return x2 < R.x2;
        return c > R.c;
    }
};

int n, m, cnt, res[MAX_N];
vector<rectangle> r;
vector<int> g[MAX_N];
int ID[MAX_N][2];
set<int> T[MAX_N];
pair<int, int> st[MAX_N*4];

int read_int() {
    char c;
    for (c = getchar(); c<'0' || c>'9'; c = getchar());
    int res = c - '0';
    for (c = getchar(); '0'<=c && c<='9'; c = getchar())
        res = res * 10 + c - '0';
    return res;
}

void enter() {
    n = read_int();
    m = read_int();
    int nVertices = 0;
    for (int i=1; i<=n; ++i) {
        int x1 = read_int();
        int y1 = read_int();
        int x2 = read_int();
        int y2 = read_int();
        r.push_back(rectangle(x1, y1, x2, y2, 0, ++nVertices));
    }
    for (int i=1; i<=m; ++i) {
        int x = read_int();
        int y = read_int();
        int k = read_int();
        r.push_back(rectangle(x, y, x, y, k, ++nVertices));
    }
    r.push_back(rectangle(1, 1, INF, INF, 0, ++nVertices));
}

void compress() {
    vector<pair<pair<int, int>, int> > b;
    sort(r.begin(), r.end());
    for (int i=0; i<r.size(); ++i) {
        b.push_back(make_pair(make_pair(r[i].y1, -r[i].x2), i));
        b.push_back(make_pair(make_pair(r[i].y2, r[i].x2), i));
    }
    sort(b.begin(), b.end());
    for (int i=0; i<b.size(); ++i) {
        cnt += (i == 0 || b[i].first != b[i-1].first);
        if (b[i].first.second < 0)
            ID[b[i].second][0] = cnt;
        else
            ID[b[i].second][1] = cnt;
    }
}

void upd(int pos, pair<int, int> val, int l, int r, int id) {
    if (pos < l || pos > r)
        return;
    if (pos == l && pos == r) {
        st[id] = val;
        return;
    }
    int mid = (l + r) / 2;
    upd(pos, val, l, mid, id*2);
    upd(pos, val, mid+1, r, id*2+1);
    st[id] = max(st[id*2], st[id*2+1]);
}

pair<int, int> get(int u, int v, int l, int r, int id) {
    if (v<l || u>r)
        return make_pair(0, 0);
    if (u<=l && r<=v)
        return st[id];
    int mid = (l + r) / 2;
    return max(get(u, v, l, mid, id*2), get(u, v, mid+1, r, id*2+1));
}

void build_tree() {
    for (int i=0; i<r.size(); ++i) {
        //cerr << ID[i][0] << ' ' << ID[i][1] << '\n';
        if (r[i].c == 0) {
            while (true) {
                pair<int, int> tmp = get(ID[i][0], ID[i][1], 1, cnt, 1);
                if (tmp.first < r[i].x1)
                    break;
                g[i].push_back(tmp.second);
                upd(ID[tmp.second][0], make_pair(0, 0), 1, cnt, 1);
            }
        }
        upd(ID[i][0], make_pair(r[i].x1, i), 1, cnt, 1);
    }
}

void Merge(int u, int v) {
    if (T[u].size() < T[v].size())
        swap(T[u], T[v]);
    for (auto x : T[v])
        T[u].insert(x);
}

void solve(int u, int par) {
    if (r[u].c)
        T[u].insert(r[u].c);
    for (auto v : g[u]) {
        if (v != par) {
            solve(v, u);
            Merge(u, v);
        }
    }
    res[r[u].id] = T[u].size();
}

int main() {
    //freopen("paintball.inp", "r", stdin);
    //freopen("paintball.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    enter();
    compress();
    build_tree();
    solve(r.size()-1, 0);
    for (int i=1; i<=n; ++i)
        cout << res[i] << '\n';
}

Compilation message

plahte.cpp: In function 'void compress()':
plahte.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<r.size(); ++i) {
                   ~^~~~~~~~~
plahte.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<b.size(); ++i) {
                   ~^~~~~~~~~
plahte.cpp: In function 'void build_tree()':
plahte.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<r.size(); ++i) {
                   ~^~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 24796 KB Output is correct
2 Correct 139 ms 27184 KB Output is correct
3 Correct 18 ms 27184 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 28812 KB Output is correct
2 Correct 154 ms 30288 KB Output is correct
3 Correct 14 ms 30288 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 41944 KB Output is correct
2 Correct 271 ms 42420 KB Output is correct
3 Correct 14 ms 42420 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 83132 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 2028 ms 88600 KB Time limit exceeded
2 Halted 0 ms 0 KB -