oj.uz

답안 #768193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768193 2023-06-27T16:45:54 Z danikoynov Plahte (COCI17_plahte) C++14
160 / 160
 547 ms 469580 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 80100;
stack < pair < int, int > > tree[8 * maxn];
void update(int root, int left, int right, int qleft, int qright, int val, int tm)
{
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        if (val == -1)
            tree[root].pop();
        else
            tree[root].push({tm, val});
        return;
    }

    int mid = (left + right ) / 2;
    update(root * 2, left, mid, qleft, qright, val, tm);
    update(root * 2 + 1, mid + 1, right, qleft, qright, val, tm);
}

pair < int, int > query(int root, int left, int right, int pos)
{
    pair < int, int > ans = {-1e9, -1};
    if (!tree[root].empty())
        ans = max(ans, tree[root].top());
    if (left == right)
        return ans;

    int mid = (left + right) / 2;
    if (pos <= mid)
        ans = max(ans, query(root * 2, left, mid, pos));
    else
        ans = max(ans, query(root * 2 + 1, mid + 1, right, pos));

    return ans;
}

struct point
{
    int x, y;
    void input()
    {
        cin >> x >> y;
    }
};

struct rectangle
{
    point A, B;


    void input()
    {
        A.input();
        B.input();
    }
};

struct line
{
    point cor;
    int len, type, idx;
};

int n, m, col[maxn];
rectangle r[maxn];
point s[maxn];

void read_data()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        r[i].input();

    for (int i = 1; i <= m; i ++)
        s[i].input(), cin >> col[i];
}

int xcor, ycor;
void compress_data()
{
    vector < int > dx, dy, dc;
    for (int i = 1; i <= n; i ++)
    {
        dx.push_back(r[i].A.x);
        dx.push_back(r[i].B.x);
        dy.push_back(r[i].A.y);
        dy.push_back(r[i].B.y);
    }
    for (int i = 1; i <= m; i ++)
    {
        dx.push_back(s[i].x);
        dy.push_back(s[i].y);
        dc.push_back(col[i]);
    }

    sort(dx.begin(), dx.end());
    sort(dy.begin(), dy.end());
    sort(dc.begin(), dc.end());

    dx.erase(unique(dx.begin(), dx.end()), dx.end());
    dy.erase(unique(dy.begin(), dy.end()), dy.end());
    dc.erase(unique(dc.begin(), dc.end()), dc.end());

    xcor = dx.size();
    ycor = dy.size();

    unordered_map < int, int > mx, my, mc;
    for (int i = 0; i < dx.size(); i ++)
        mx[dx[i]] = i + 1;
    for (int i = 0; i < dy.size(); i ++)
        my[dy[i]] = i + 1;
    for (int i = 0; i < dc.size(); i ++)
        mc[dc[i]] = i + 1;

    for (int i = 1; i <= n; i ++)
    {
        r[i].A.x = mx[r[i].A.x];
        r[i].A.y = my[r[i].A.y];
        r[i].B.x = mx[r[i].B.x];
        r[i].B.y = my[r[i].B.y];
    }

    for (int i = 1; i <= m; i ++)
    {
        s[i].x = mx[s[i].x];
        s[i].y = my[s[i].y];
        col[i] = mc[col[i]];
    }

}

bool cmp(const line &l1, const line &l2)
{
    if (l1.cor.x != l2.cor.x)
        return l1.cor.x < l2.cor.x;
    return l1.type > l2.type;
}

void creat_events(vector < line > &events)
{
    for (int i = 1; i <= n; i ++)
    {
        line l;
        l.cor.x = r[i].A.x;
        l.cor.y = r[i].A.y;
        l.idx = i;
        l.len = r[i].B.y - r[i].A.y;
        l.type = 1;
        events.push_back(l);
        l.cor.x = r[i].B.x;
        l.type = -1;
        events.push_back(l);
    }

    for (int i = 1; i <= m; i ++)
    {
        line l;
        l.cor = s[i];
        l.len = 0;
        l.type = 0;
        l.idx = i;
        events.push_back(l);
    }

    sort(events.begin(), events.end(), cmp);
}

vector < int > adj[maxn];
int sub[maxn], deg[maxn];
vector < int > upd[maxn];
void sweep_line()
{
    vector < line > events;
    creat_events(events);

    for (int i = 0; i < events.size(); i ++)
    {
        line cur = events[i];
        ///cout << "event " << i << " " << cur.type << " " << cur.cor.x << " " << cur.cor.y << " " << cur.cor.y + cur.len << endl;
        if (cur.type == 1)
        {
            int par = query(1, 1, ycor, cur.cor.y).second;
            if (par != -1)
                adj[par].push_back(cur.idx), deg[cur.idx] ++;
            update(1, 1, ycor, cur.cor.y, cur.cor.y + cur.len, cur.idx, i);
        }
        else if (cur.type == -1)
        {
            update(1, 1, ycor, cur.cor.y, cur.cor.y + cur.len, -1, -1);
        }
        else
        {
            int par = query(1, 1, ycor, cur.cor.y).second;
            if (par != -1)
            {
                upd[par].push_back(col[cur.idx]);
            }
            ///cout << "here " << par << endl;
        }
    }
}

int used[maxn], ans[maxn];

void calc(int v)
{
    sub[v] = 1;
    for (int u : adj[v])
    {
        calc(u);
        sub[v] += sub[u];
    }
}

unordered_set < int > st[maxn];
void dfs(int v)
{
    int mx = -1;
    for (int u : adj[v])
    {
        if (mx == -1 || sub[u] > sub[mx])
            mx = u;
    }

    for (int u : adj[v])
    {
        dfs(u);
    }

    if (mx != -1)
    swap(st[mx], st[v]);

    for (int d : upd[v])
        st[v].insert(d);
    for (int u : adj[v])
    {
        if (u != mx)
            for (int d : st[u])
            st[v].insert(d);
    }

    ans[v] = st[v].size();
}

void traverse_graph()
{
    for (int i = 1; i <= n; i ++)
        if (deg[i] == 0)
            adj[0].push_back(i);

    calc(0);
    dfs(0);

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << endl;
}
void solve()
{
    read_data();
    compress_data();
    sweep_line();
    traverse_graph();
}

int main()
{
    ///freopen("test.txt", "r", stdin);
    speed();
    solve();
    return 0;
}

Compilation message

plahte.cpp: In function 'void compress_data()':
plahte.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int i = 0; i < dx.size(); i ++)
      |                     ~~^~~~~~~~~~~
plahte.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < dy.size(); i ++)
      |                     ~~^~~~~~~~~~~
plahte.cpp:135:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     for (int i = 0; i < dc.size(); i ++)
      |                     ~~^~~~~~~~~~~
plahte.cpp: In function 'void sweep_line()':
plahte.cpp:199:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |     for (int i = 0; i < events.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 447760 KB Output is correct
2 Correct 288 ms 449096 KB Output is correct
3 Correct 198 ms 439796 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 450280 KB Output is correct
2 Correct 307 ms 450440 KB Output is correct
3 Correct 211 ms 439900 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 455700 KB Output is correct
2 Correct 390 ms 457608 KB Output is correct
3 Correct 200 ms 439768 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 547 ms 465316 KB Output is correct
2 Correct 547 ms 469580 KB Output is correct
3 Correct 206 ms 439884 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 534 ms 465512 KB Output is correct
2 Correct 521 ms 467944 KB Output is correct
3 Correct 206 ms 439880 KB Output is correct