Submission #598386

# Submission time Handle Problem Language Result Execution time Memory
598386 2022-07-18T08:27:52 Z imtore 수족관 3 (KOI13_aqua3) C++14
Compilation error
0 ms 0 KB
#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;
}

Compilation message

aqua3.cpp:11:1: error: 'vector' does not name a type
   11 | vector<int> X, Y;
      | ^~~~~~
aqua3.cpp:31:1: error: 'vector' does not name a type
   31 | vector<int> edge[150021];
      | ^~~~~~
aqua3.cpp: In function 'void dfs(int)':
aqua3.cpp:40:14: error: 'edge' was not declared in this scope
   40 |  for(int u : edge[v]) dfs(u);
      |              ^~~~
aqua3.cpp: At global scope:
aqua3.cpp:53:2: error: 'vector' does not name a type
   53 |  vector<Node> tree;
      |  ^~~~~~
aqua3.cpp: In constructor 'Segment_Tree::Segment_Tree(int)':
aqua3.cpp:57:3: error: 'tree' was not declared in this scope; did you mean 'free'?
   57 |   tree.assign(ele<<1, Node());
      |   ^~~~
      |   free
aqua3.cpp: In member function 'void Segment_Tree::spread(int)':
aqua3.cpp:62:3: error: 'tree' was not declared in this scope; did you mean 'free'?
   62 |   tree[w<<1].mx += tree[w].lazy;
      |   ^~~~
      |   free
aqua3.cpp: In member function 'void Segment_Tree::update(int)':
aqua3.cpp:72:6: error: 'tree' was not declared in this scope; did you mean 'free'?
   72 |   if(tree[w<<1].mx > tree[w<<1|1].mx){
      |      ^~~~
      |      free
aqua3.cpp: In member function 'void Segment_Tree::insert(int, int, int, int, int, long long int)':
aqua3.cpp:85:4: error: 'tree' was not declared in this scope; did you mean 'free'?
   85 |    tree[w].mx += v;
      |    ^~~~
      |    free
aqua3.cpp:93:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |   int m = l+r>>1;
      |           ~^~
aqua3.cpp: In function 'int main()':
aqua3.cpp:107:3: error: 'X' was not declared in this scope
  107 |   X.push_back(x);
      |   ^
aqua3.cpp:108:3: error: 'Y' was not declared in this scope
  108 |   Y.push_back(y);
      |   ^
aqua3.cpp:112:2: error: 'X' was not declared in this scope
  112 |  X.erase(unique(X.begin(), X.end()), X.end());
      |  ^
aqua3.cpp:113:2: error: 'Y' was not declared in this scope
  113 |  Y.erase(unique(Y.begin(), Y.end()), Y.end());
      |  ^
aqua3.cpp:118:2: error: 'vector' was not declared in this scope
  118 |  vector<Line> L;
      |  ^~~~~~
aqua3.cpp:5:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    4 | #include <algorithm>
  +++ |+#include <vector>
    5 | #define LL long long
aqua3.cpp:118:13: error: expected primary-expression before '>' token
  118 |  vector<Line> L;
      |             ^
aqua3.cpp:118:15: error: 'L' was not declared in this scope
  118 |  vector<Line> L;
      |               ^
aqua3.cpp:128:4: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and '<brace-enclosed initializer list>')
  128 |  mp[{X.front(), X.back()}] = ++piv;
      |    ^
In file included from /usr/include/c++/10/map:61,
                 from aqua3.cpp:3:
/usr/include/c++/10/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::map<std::pair<int, int>, int>::key_type&&' {aka 'std::pair<int, int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
aqua3.cpp:140:10: error: expected primary-expression before 'int'
  140 |   vector<int> vc;
      |          ^~~
aqua3.cpp:159:4: error: 'vc' was not declared in this scope
  159 |    vc.push_back(l.sx);
      |    ^~
aqua3.cpp:177:5: error: 'edge' was not declared in this scope
  177 |     edge[p].push_back(piv);
      |     ^~~~
aqua3.cpp:182:15: error: 'vc' was not declared in this scope
  182 |   for(int x : vc){
      |               ^~
aqua3.cpp:188:3: error: 'vc' was not declared in this scope
  188 |   vc.clear();
      |   ^~
aqua3.cpp:210:14: error: 'struct Segment_Tree' has no member named 'tree'
  210 |   sum += SGT.tree[1].mx;
      |              ^~~~
aqua3.cpp:214:21: error: 'struct Segment_Tree' has no member named 'tree'
  214 |   for(int v = V[SGT.tree[1].idx]; v; v = par[v]){
      |                     ^~~~
aqua3.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
aqua3.cpp:106:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~
aqua3.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~