oj.uz

Submission #200919

# Submission time Handle Problem Language Result Execution time Memory
200919 2020-02-08T14:57:47 Z SamAnd Plahte (COCI17_plahte) C++17
160 / 160
 476 ms 42084 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int N = 80004;
struct ban
{
    int x;
    int ty;
    int i;
    ban(){}
    ban(int x, int ty, int i)
    {
        this->x = x;
        this->ty = ty;
        this->i = i;
    }
};
bool operator<(const ban& a, const ban& b)
{
    if (a.x < b.x)
        return true;
    if (a.x > b.x)
        return false;
    return a.ty < b.ty;
}

int n, m;
int x1[N], y1[N], x2[N], y2[N];
int x[N], y[N], g[N];

int t[N * 12];
void shi(int pos)
{
    if (t[pos] == -1)
        return;
    t[pos * 2] = t[pos];
    t[pos * 2 + 1] = t[pos];
    t[pos] = -1;
}

void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        t[pos] = y;
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
}
int qry(int tl, int tr, int x, int pos)
{
    if (tl == tr)
        return t[pos];
    shi(pos);
    int m = (tl + tr) / 2;
    if (x <= m)
        return qry(tl, m, x, pos * 2);
    else
        return qry(m + 1, tr, x, pos * 2 + 1);
}

int p[N];
int u[N];
vector<int> a[N];

int ans[N];
set<int> s[N];
void dfs(int x)
{
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs(h);
        if (s[h].size() > s[x].size())
            swap(s[x], s[h]);
        for (set<int>::iterator it = s[h].begin(); it != s[h].end(); ++it)
            s[x].insert(*it);
    }
    ans[x] = s[x].size();
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &x[i], &y[i], &g[i]);
    ///////////////////////////////////////////////////////
    vector<int> vv;
    map<int, int> mp;
    int z = 0;
    for (int i = 1; i <= n; ++i)
    {
        vv.push_back(y1[i]);
        vv.push_back(y2[i]);
    }
    for (int i = 1; i <= m; ++i)
        vv.push_back(y[i]);
    sort(vv.begin(), vv.end());
    for (int i = 0; i < vv.size(); ++i)
    {
        if (!i || vv[i] != vv[i - 1])
            mp[vv[i]] = ++z;
    }
    for (int i = 1; i <= n; ++i)
    {
        y1[i] = mp[y1[i]];
        y2[i] = mp[y2[i]];
    }
    for (int i = 1; i <= m; ++i)
        y[i] = mp[y[i]];
    ////////////////////////////////////////////////////////////
    vector<ban> v;
    for (int i = 1; i <= n; ++i)
    {
        v.push_back(ban(x1[i], 0, i));
        v.push_back(ban(x2[i], 2, i));
    }
    for (int i = 1; i <= m; ++i)
    {
        v.push_back(ban(x[i], 1, i));
    }
    sort(v.begin(), v.end());
    for (int ii = 0; ii < v.size(); ++ii)
    {
        int ty = v[ii].ty;
        int i = v[ii].i;
        if (ty == 0)
        {
            p[i] = qry(1, z, y1[i], 1);
            ubd(1, z, y1[i], y2[i], i, 1);
        }
        else if (ty == 1)
        {
            u[i] = qry(1, z, y[i], 1);
        }
        else
        {
            ubd(1, z, y1[i], y2[i], p[i], 1);
        }
    }
    ////////////////////////////////////////////////
    for (int i = 1; i <= n; ++i)
        a[p[i]].push_back(i);
    for (int i = 1; i <= m; ++i)
        s[u[i]].insert(g[i]);
    dfs(0);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vv.size(); ++i)
                     ~~^~~~~~~~~~~
plahte.cpp:134:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < v.size(); ++ii)
                      ~~~^~~~~~~~~~
plahte.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x[i], &y[i], &g[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 17132 KB Output is correct
2 Correct 125 ms 17640 KB Output is correct
3 Correct 9 ms 6008 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 19256 KB Output is correct
2 Correct 150 ms 18536 KB Output is correct
3 Correct 9 ms 6008 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 29156 KB Output is correct
2 Correct 254 ms 25188 KB Output is correct
3 Correct 9 ms 6008 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 42084 KB Output is correct
2 Correct 467 ms 38708 KB Output is correct
3 Correct 8 ms 6008 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 40156 KB Output is correct
2 Correct 459 ms 36700 KB Output is correct
3 Correct 9 ms 6008 KB Output is correct