| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 745667 |
2023-05-20T20:58:53 Z |
esomer |
Plahte (COCI17_plahte) |
C++17 |
|
1558 ms |
79060 KB |
#include<bits/stdc++.h>
using namespace std;
//~ #define endl "\n"
typedef long long ll;
typedef long double ld;
const int MOD = 1e9 + 7;
struct segTree{
vector<pair<int, int>> v;
vector<set<pair<int, int>>> all;
int size;
void init(int n){
size = 1;
while(size < n) size *= 2;
v.assign(2 * size, {1e9, 1e9});
all.resize(2 * size);
}
void sett(int i, pair<int, int> p, int x, int lx, int rx){
if(rx - lx == 1){
all[x].insert(p);
v[x] = *all[x].begin();
return;
}
int m = (lx + rx) / 2;
if(i < m) sett(i, p, 2 * x + 1, lx, m);
else sett(i, p, 2 * x + 2, m, rx);
v[x] = min(v[2 * x + 1], v[2 * x + 2]);
}
void sett(int i, pair<int, int> p){
sett(i, p, 0, 0, size);
}
void eras(int i, pair<int, int> p, int x, int lx, int rx){
if(rx - lx == 1){
all[x].erase(p);
if((int)all[x].size() > 0) v[x] = *all[x].begin();
else v[x] = {1e9, 1e9};
return;
}
int m = (lx + rx) / 2;
if(i < m) eras(i, p, 2 * x + 1, lx, m);
else eras(i, p, 2 * x + 2, m, rx);
v[x] = min(v[2 * x + 1], v[2 * x + 2]);
}
void eras(int i, pair<int, int> p){
eras(i, p, 0, 0, size);
}
pair<int, int> calc(int l, int r, int x, int lx, int rx){
if(lx >= l && rx <= r) return v[x];
else if(lx >= r || rx <= l) return {1e9, 1e9};
int m = (lx + rx) / 2;
pair<int, int> p1 = calc(l, r, 2 * x + 1, lx, m);
pair<int, int> p2 = calc(l, r, 2 * x + 2, m, rx);
return min(p1, p2);
}
pair<int, int> calc(int l, int r){
return calc(l, r, 0, 0, size);
}
};
void DFS(int x, vector<vector<int>>& adj, vector<bool>& vis, vector<set<int>>& colors, vector<int>& ans){
//~ cout << "X " << x << endl;
//~ cout << "Colors: " << endl;
//~ for(int y : colors[x]) cout << y << " "; cout << endl;
vis[x] = 1;
for(int node : adj[x]){
//~ cout << "X " << x << " node " << node << endl;
if(!vis[node]){
DFS(node, adj, vis, colors, ans);
if((int)colors[node].size() > (int)colors[x].size()) swap(colors[x], colors[node]);
for(int y : colors[node]){
colors[x].insert(y);
}
//~ cout <<"X " << x << " node " << node << " colors " << endl;
//~ for(int y: colors[x]) cout << y << " "; cout << endl;
}
}
ans[x] = (int)colors[x].size();
}
void solve(){
int n, m; cin >> n >> m;
vector<tuple<int, int, int, int, int>> v(n + m);
vector<int> heights;
for(int i = 0; i < n; i++){
int a, b, c, d; cin >> a >> b >> c >> d;
v[i] = {a, d, c, b, i};
heights.push_back(b); heights.push_back(d);
}
vector<vector<int>> adj(n+m);
vector<set<int>> colors(n + m);
vector<int> deg(n+m, 0);
for(int i = 0; i < m; i++){
int a, b, c; cin >> a >> b >> c;
heights.push_back(b);
colors[n + i].insert(c);
v[n+i] = {a, 1e9, b, -1, n+i};
}
sort(v.begin(), v.end());
int mx_height = 0;
int lst = -1;
map<int, int> ind;
sort(heights.begin(), heights.end());
for(int i = 0; i < (int)heights.size(); i++){
if(heights[i] != lst){
ind[heights[i]] = mx_height;
//~ cout << "heights[i] " << heights[i] << " ind " << ind[heights[i]] << endl;
mx_height++;
}
lst = heights[i];
}
segTree st; st.init(mx_height);
priority_queue<tuple<int, int, int, int>> q;
int curr = 0;
for(int i = 0; i < n + m; i++){
//~ cout << "I " << i << endl;
while(q.empty() == false && -get<0>(q.top()) < get<0>(v[i])){
int up = ind[get<1>(q.top())];
int down = ind[get<2>(q.top())];
int id = get<3>(q.top());
//~ cout << "Removing " << get<1>(q.top()) << " " << get<2>(q.top()) << " " << get<3>(q.top()) << endl;
st.eras(up, {down, id});
q.pop();
}
int height = get<1>(v[i]);
if(get<3>(v[i]) == -1) height = get<2>(v[i]);
int lo = ind[height];
int hi = mx_height - 1;
int bst = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
pair<int, int> p = st.calc(ind[height], mid + 1);
int low = get<3>(v[i]);
if(get<3>(v[i]) == -1) low = get<2>(v[i]);
if(p.first <= ind[low]){
bst = p.second;
hi = mid - 1;
}else lo = mid + 1;
}
//~ cout << "I " << i << " ind " << get<4>(v[i]) << " bst " << bst << endl;
if(bst != -1) {adj[bst].push_back(get<4>(v[i])); deg[get<4>(v[i])]++;}
if(get<3>(v[i]) != -1){
//Add it into the segment tree.
//~ cout << "Inserting at height " << get<1>(v[i]) << " " << get<3>(v[i]) << " " << get<4>(v[i]) << endl;
q.push({-get<2>(v[i]), get<1>(v[i]), get<3>(v[i]), get<4>(v[i])});
//~ cout << "Here" << endl;
st.sett(ind[get<1>(v[i])], {ind[get<3>(v[i])], get<4>(v[i])});
//~ cout << "Here2" << endl;
}
}
//~ cout << "OUT" << endl;
vector<bool> vis(n+m, 0);
vector<int> ans(n+m);
for(int i = 0; i < n; i++){
if(!deg[i]){
DFS(i, adj, vis, colors, ans);
}
}
for(int i = 0; i < n; i++) cout << ans[i] << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//~ int tt; cin >> tt;
int tt = 1;
for(int t = 1; t <= tt; t++){
solve();
}
}
Compilation message
plahte.cpp: In function 'void solve()':
plahte.cpp:123:6: warning: unused variable 'curr' [-Wunused-variable]
123 | int curr = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
410 ms |
29820 KB |
Output is correct |
| 2 |
Correct |
418 ms |
30280 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
453 ms |
32584 KB |
Output is correct |
| 2 |
Correct |
466 ms |
31308 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
838 ms |
60400 KB |
Output is correct |
| 2 |
Correct |
883 ms |
41512 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1446 ms |
79060 KB |
Output is correct |
| 2 |
Correct |
1558 ms |
72924 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1448 ms |
76836 KB |
Output is correct |
| 2 |
Correct |
1505 ms |
71116 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
