| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 200918 | SamAnd | Plahte (COCI17_plahte) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
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;
}