| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 598386 | imtore | 수족관 3 (KOI13_aqua3) | C++14 | 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 <stdio.h>
#include <set>
#include <map>
#include <algorithm>
#define LL long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
vector<int> X, Y;
struct Line{
int sx, ex, y;
Line(int sx, int ex, int y) : sx(sx), ex(ex), y(y) {}
bool operator < (const Line &l) const {
if(y != l.y) return y > l.y;
return sx > l.sx;
}
};
struct Plane{
int sx, ex, sy, ey;
}P[150021];
map<pii, int> mp;
set<int> st1, st2;
vector<int> edge[150021];
int par[150021];
int dfn_piv;
pii dfn[150021];
int V[150021];
void dfs(int v){
dfn[v].ff = ++dfn_piv; V[dfn_piv] = v;
for(int u : edge[v]) dfs(u);
dfn[v].ss = dfn_piv;
}
struct Segment_Tree{
struct Node{
LL mx, lazy;
int idx;
Node() : mx(0), lazy(0), idx(0) {}
};
int ele;
vector<Node> tree;
Segment_Tree(int n){
for(ele = 1; ele < n; ele <<= 1);
tree.assign(ele<<1, Node());
for(int i = 1; i <= ele; i++) tree[i+ele-1].idx = i;
}
void spread(int w){
tree[w<<1].mx += tree[w].lazy;
tree[w<<1].lazy += tree[w].lazy;
tree[w<<1|1].mx += tree[w].lazy;
tree[w<<1|1].lazy += tree[w].lazy;
tree[w].lazy = 0;
}
void update(int w){
if(tree[w<<1].mx > tree[w<<1|1].mx){
tree[w].mx = tree[w<<1].mx;
tree[w].idx = tree[w<<1].idx;
}
else{
tree[w].mx = tree[w<<1|1].mx;
tree[w].idx = tree[w<<1|1].idx;
}
}
void insert(int w, int l, int r, int s, int e, LL v){
//printf("%d %d %d %d %d %lld\n", w, l, r, s, e, v);
if(s == l && e == r){
tree[w].mx += v;
tree[w].lazy += v;
//update(w);
return;
}
spread(w);
int m = l+r>>1;
if(s <= m) insert(w<<1, l, m, s, min(e, m), v);
if(e > m) insert(w<<1|1, m+1, r, max(s, m+1), e, v);
update(w);
}
};
int main(){
int n, k;
scanf("%d", &n);
for(int i = 1; i <= n; i++){
int x, y; scanf("%d %d", &x, &y);
X.push_back(x);
Y.push_back(y);
}
scanf("%d", &k);
X.erase(unique(X.begin(), X.end()), X.end());
Y.erase(unique(Y.begin(), Y.end()), Y.end());
//for(int x : X) printf("%d ", x); printf("\n");
//for(int y : Y) printf("%d ", y); printf("\n");
vector<Line> L;
for(int i = 1; i < X.size(); i++) L.push_back(Line(X[i-1], X[i], Y[i]));
//for(Line l : L) printf("%d %d %d\n", l.sx, l.ex, l.y); printf("\n");
sort(L.begin(), L.end());
//for(Line l : L) printf("%d %d %d\n", l.sx, l.ex, l.y); printf("\n");
int piv = 0;
mp[{X.front(), X.back()}] = ++piv;
P[piv].sx = X.front();
P[piv].ex = X.back();
P[piv].sy = 0;
st1.insert(X.front());
st1.insert(X.back());
while(!L.empty()){
int y = L.back().y;
vector<int> vc;
while(!L.empty() && L.back().y == y){
Line l = L.back(); L.pop_back();
set<int>::iterator it2 = st1.lower_bound(l.ex);
set<int>::iterator it1 = it2; it1--;
int p = mp[{*it1, *it2}];
P[p].ey = y;
if(st2.find(*it1) == st2.end()) st2.insert(*it1);
else st2.erase(*it1);
if(st2.find(*it2) == st2.end()) st2.insert(*it2);
else st2.erase(*it2);
if(st2.find(l.sx) == st2.end()) st2.insert(l.sx);
else st2.erase(l.sx);
if(st2.find(l.ex) == st2.end()) st2.insert(l.ex);
else st2.erase(l.ex);
vc.push_back(l.sx);
vc.push_back(l.ex);
}
for(set<int>::iterator it21 = st2.begin(); it21 != st2.end(); it21++, it21++){
set<int>::iterator it22 = it21; it22++;
set<int>::iterator it12 = st1.lower_bound(*it22);
set<int>::iterator it11 = it12; it11--;
if(*it11 != *it21 || *it12 != *it22){
mp[{*it21, *it22}] = ++piv;
P[piv].sx = *it21;
P[piv].ex = *it22;
P[piv].sy = y;
int p = mp[{*it11, *it12}];
edge[p].push_back(piv);
par[piv] = p;
}
}
for(int x : vc){
if(st1.find(x) == st1.end()) st1.insert(x);
else st1.erase(x);
}
st2.clear();
vc.clear();
}
/*
for(int i = 1; i <= piv; i++){
printf("%d : ", i); for(int u : edge[i]) printf("%d ", u); printf(": ");
printf("%d %d %d %d\n", P[i].sx, P[i].ex, P[i].sy, P[i].ey);
}
printf("\n");
*/
dfs(1);
//for(int i = 1; i <= piv; i++) printf("%d : %d %d\n", i, dfn[i].ff, dfn[i].ss);
Segment_Tree SGT(piv);
for(int i = 1; i <= piv; i++){
LL p = (LL)(P[i].sx-P[i].ex)*(P[i].sy-P[i].ey);
SGT.insert(1, 1, SGT.ele, dfn[i].ff, dfn[i].ss, p);
//for(int i = 1; i < (SGT.ele<<1); i++) printf("SGT %d : %d %lld\n", i, SGT.tree[i].idx, SGT.tree[i].mx);
}
LL sum = 0;
while(k--){
sum += SGT.tree[1].mx;
//for(int i = 1; i < (SGT.ele<<1); i++) printf("SGT %d : %d %lld\n", i, SGT.tree[i].idx, SGT.tree[i].mx);
for(int v = V[SGT.tree[1].idx]; v; v = par[v]){
LL p = (LL)(P[v].sx-P[v].ex)*(P[v].sy-P[v].ey);
SGT.insert(1, 1, SGT.ele, dfn[v].ff, dfn[v].ss, -p);
//printf("%d %lld\n", v, p);
}
//printf("%lld\n", sum);
}
printf("%lld", sum);
return 0;
}