| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1109999 |
2024-11-08T12:05:46 Z |
PVSekhar |
Plahte (COCI17_plahte) |
C++17 |
|
454 ms |
66792 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 80000 + 2;
template<class T>
struct Point{
T x, y;
Point (const ll &x_ = 0, const ll &y_ = 0) : x(x_), y(y_) {};
bool operator<(const Point &p) const{
return x < p.x || (x == p.x && y < p.y);
}
bool operator==(const Point &p) const{
return x == p.x && y == p.y;
}
};
using Pt = Point<ll>;
struct Line {
ll x1, y1, x2, y2, ind;
Line (const ll &x1_ = 0, const ll &y1_ = 0, const ll &x2_ = 0, const ll &y2_ = 0, const ll &ind_ = 0) : x1(x1_), y1(y1_), x2(x2_), y2(y2_), ind(ind_) {};
bool operator==(const Line &l) const {
return ind == l.ind;
}
bool operator<(const Line &l) const {
return ind != l.ind && (x1 < l.x1 || (x1 == l.x1 && y1 < l.y1));
}
};
struct SEGTREE {
ll def = N - 1;
vector<ll> tree, lazy;
SEGTREE(int n_) {
for (int i = 0; i < 4 * n_; i++) tree.push_back(0);
for (int i = 0; i < 4 * n_; i++) lazy.push_back(def);
}
void prop(int node, int i, int j) {
if (lazy[node] == -1) return;
tree[node] = (j - i + 1) * lazy[node];
if (i != j) {
lazy[node << 1] = lazy[node];
lazy[node << 1 | 1] = lazy[node];
}
lazy[node] = -1;
}
void update(int node, int i, int j, int l, int r, int val) {
if (i > j || i > r || l > r || l > j) return;
if (l <= i && j <= r) {
lazy[node] = val;
prop(node, i, j);
return;
}
int mid = (i + j) / 2;
prop(node << 1, i, mid);
prop(node << 1 | 1, mid + 1, j);
update(node << 1, i, mid, l, r, val);
update(node << 1 | 1, mid + 1, j, l, r, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
int query(int node, int i, int j, int ind) {
prop(node, i, j);
if (i == j) {
return tree[node];
}
int mid = (i + j) / 2;
prop(node << 1, i, mid);
prop(node << 1 | 1, mid + 1, j);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
if (ind <= mid) return query(node << 1, i, mid, ind);
else return query(node << 1 | 1, mid + 1, j, ind);
}
} segtree(3 * N);
ll n, m;
vector<Line> recs;
vector<set<ll>> c_set(N);
vector<ll> c_ind(N), p(N, N - 1), ans(N, -1);
vector<pair<Pt, ll>> pts;
vector<vector<ll>> edges(N);
map<ll, ll> y_ind;
void merge(ll node, ll parent) {
if (c_set[c_ind[node]].size() > c_set[c_ind[parent]].size()) {
for (ll x : c_set[c_ind[parent]]) c_set[c_ind[node]].insert(x);
c_ind[parent] = c_ind[node];
} else {
for (ll x : c_set[c_ind[node]]) c_set[c_ind[parent]].insert(x);
}
}
ll find_p(ll y) {
return segtree.query(1, 1, 3 * N, y);
}
void sweep() {
set<Pt> s;
Pt pt;
ll ind;
for (auto x : pts) {
pt = x.first, ind = x.second;
ll par = find_p(y_ind[pt.y]);
if (ind < 0) {
if (par != N - 1) c_set[c_ind[par]].insert(ind);
} else if (s.find(Pt(recs[ind].x1, recs[ind].y1)) == s.end()) {
s.insert(pt);
edges[ind].push_back(par);
edges[par].push_back(ind);
segtree.update(1, 1, 3 * N, y_ind[recs[ind].y1], y_ind[recs[ind].y2], ind);
} else {
s.erase(Pt(recs[ind].x1, recs[ind].y1));
segtree.update(1, 1, 3 * N, y_ind[recs[ind].y1], y_ind[recs[ind].y2], p[ind]);
}
}
}
void dfs(ll node, ll parent) {
for (ll child : edges[node]) {
if (child == parent) continue;
dfs(child, node);
}
if (node != N - 1) ans[node] = c_set[c_ind[node]].size();
if (node != N - 1 && parent != N - 1) merge(node, parent);
}
void solve() {
ll a, b, c, d;
cin >> n >> m;
vector<ll> ys;
for (ll i = 0; i < n; i++) {
cin >> a >> b >> c >> d;
recs.push_back(Line(a, b, c, d, i));
pts.push_back(make_pair(Pt(a, b), i));
pts.push_back(make_pair(Pt(c, d), i));
ys.push_back(b);
ys.push_back(d);
c_ind[i] = i;
}
for (ll i = 0; i < m; i++) {
cin >> a >> b >> c;
ys.push_back(b);
pts.push_back(make_pair(Pt(a, b), -c));
}
sort(pts.begin(), pts.end());
sort(ys.begin(), ys.end());
for (int i = 0; i < ys.size(); i++) {
y_ind[ys[i]] = i + 1;
}
sweep();
dfs(N - 1, -1);
for (ll i = 0; i < n; i++) cout << ans[i] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t = 1;
// cin >> t;
while(t--) {
solve();
}
return 0;
}
Compilation message
plahte.cpp: In function 'void solve()':
plahte.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int i = 0; i < ys.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
37408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
141 ms |
39712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
254 ms |
51744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
454 ms |
66792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
428 ms |
65436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
