| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1078625 |
2024-08-28T01:19:56 Z |
HiepVu217 |
Plahte (COCI17_plahte) |
C++17 |
|
192 ms |
80720 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 17;
int n, m, sz, b[N];
int st[N], lz[N];
int pre[N], ans[N], z[N];
vector <int> adj[N];
map <int, bool> c[N];
struct rect
{
int x, l, r, t, id;
} a[N];
bool cmp (rect x, rect y)
{
if (x.x != y.x)
{
return x.x < y.x;
}
return x.t > y.t;
}
void build (int id, int l, int r)
{
lz[id] = -1;
if (l == r)
{
return;
}
int mid = l + r >> 1;
build (id * 2, l, mid);
build (id * 2 + 1, mid + 1, r);
}
void down (int id)
{
if (lz[id] < 0)
{
return;
}
st[id * 2] = lz[id];
st[id * 2 + 1] = lz[id];
lz[id * 2] = lz[id];
lz[id * 2 + 1] = lz[id];
lz[id] = -1;
}
void update (int id, int l, int r, int u, int v, int z)
{
if (u > r || l > v)
{
return;
}
if (u <= l && v >= r)
{
st[id] = lz[id] = z;
return;
}
int mid = l + r >> 1;
down(id);
update (id * 2, l, mid, u, v, z);
update (id * 2 + 1, mid + 1, r, u, v, z);
st[id] = max (st[id * 2], st[id * 2 + 1]);
}
int get (int id, int l, int r, int u, int v)
{
if (u > r || l > v)
{
return 0;
}
if (u <= l && v >= r)
{
return st[id];
}
int mid = l + r >> 1;
down(id);
return max (get (id * 2, l, mid, u, v), get (id * 2 + 1, mid + 1, r, u, v));
}
void dfs (int u, int pr)
{
for (int v: adj[u])
{
if (v == pr)
{
continue;
}
if (ans[v] < 0)
{
dfs (v, u);
}
if (c[v].size() > c[u].size())
{
swap (c[u], c[v]);
}
for (auto [x, s]: c[v])
{
c[u][x] = 1;
}
}
ans[u] = c[u].size();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1, u, v, x, y; i <= n; ++i)
{
cin >> u >> v >> x >> y;
a[++sz] = {u, v, y, 1, i};
b[sz] = v;
a[++sz] = {x, v, y, -1, i};
b[sz] = y;
}
for (int i = 1, x, y, k; i <= m; ++i)
{
cin >> x >> y >> k;
a[++sz] = {x, y, y, 0, k};
b[sz] = y;
}
sort (a + 1, a + sz + 1, cmp);
sort (b + 1, b + sz + 1);
build (1, 1, sz);
for (int i = 1; i <= sz; ++i)
{
auto [x, l, r, t, id] = a[i];
l = lower_bound (b + 1, b + sz + 1, l) - b;
r = lower_bound (b + 1, b + sz + 1, r) - b;
if (t > 0)
{
pre[id] = get (1, 1, sz, l, r);
if (!pre[id])
{
update (1, 1, sz, l, r, id);
continue;
}
if (pre[id] < id)
{
update (1, 1, sz, l, r, id);
adj[pre[id]].push_back(id);
continue;
}
z[id] = pre[id];
continue;
}
if (t < 0)
{
update (1, 1, sz, l, r, pre[id]);
continue;
}
int z = get (1, 1, sz, l, r);
c[z][id] = 1;
}
memset (ans, -1, sizeof(ans));
for (int i = 1; i <= n; ++i)
{
if (ans[i] < 0)
{
dfs (i, 0);
}
}
for (int i = 1; i <= n; ++i)
{
if (z[i])
{
ans[i] = ans[z[i]];
}
}
for (int i = 1; i <= n; ++i)
{
cout << ans[i] << "\n";
}
}
Compilation message
plahte.cpp: In function 'void build(int, int, int)':
plahte.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | int mid = l + r >> 1;
| ~~^~~
plahte.cpp: In function 'void update(int, int, int, int, int, int)':
plahte.cpp:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | int mid = l + r >> 1;
| ~~^~~
plahte.cpp: In function 'int get(int, int, int, int, int)':
plahte.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
78 ms |
36944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
37096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
122 ms |
41300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
45648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
146 ms |
80720 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
