oj.uz

Submission #598420

# Submission time Handle Problem Language Result Execution time Memory
598420 2022-07-18T10:31:17 Z imtore 수족관 3 (KOI13_aqua3) C++14
100 / 100
 552 ms 42528 KB 
#include <stdio.h>
#include <map>
#include <set>
#include <vector>
#include <queue>
#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];

priority_queue<LL> pq;

LL dfs(int v){
	LL mx = 0;
	for(int u : edge[v]){
		LL res = dfs(u);

		if(mx < res){
			if(mx) pq.push(mx);
			mx = res;
		}
		else pq.push(res);
	}
	return mx+(LL)(P[v].sx-P[v].ex)*(P[v].sy-P[v].ey);
}

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;
		set<int> st;
		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--;

			P[mp[{*it1, *it2}]].ey = y;

			if(st.find(*it1) == st.end()) st.insert(*it1);
			if(st.find(*it2) == st.end()) st.insert(*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(int x : st){
			if(st2.find(x) == st2.end()) st2.insert(x);
			else st2.erase(x);
		}
		st.clear();

		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--;

			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");
*/
	pq.push(dfs(1));

	LL sum = 0;
	for(;!pq.empty() && k--; pq.pop()) sum += pq.top();

	printf("%lld", sum);

	return 0;
}

Compilation message

aqua3.cpp: In function 'int main()':
aqua3.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 1; i < X.size(); i++) L.push_back(Line(X[i-1], X[i], Y[i]));
      |                 ~~^~~~~~~~~~
aqua3.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
aqua3.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~
aqua3.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 3 ms 3832 KB Output is correct
3 Correct 3 ms 3796 KB Output is correct
4 Correct 3 ms 3796 KB Output is correct
5 Correct 3 ms 3924 KB Output is correct
6 Correct 3 ms 3924 KB Output is correct
7 Correct 4 ms 3836 KB Output is correct
8 Correct 3 ms 3836 KB Output is correct
9 Correct 3 ms 3924 KB Output is correct
10 Correct 3 ms 3924 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4180 KB Output is correct
2 Correct 6 ms 4180 KB Output is correct
3 Correct 6 ms 4232 KB Output is correct
4 Correct 7 ms 4224 KB Output is correct
5 Correct 8 ms 4308 KB Output is correct
6 Correct 5 ms 4356 KB Output is correct
7 Correct 5 ms 4436 KB Output is correct
8 Correct 5 ms 4424 KB Output is correct
9 Correct 7 ms 4220 KB Output is correct
10 Correct 6 ms 4292 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 26036 KB Output is correct
2 Correct 388 ms 30492 KB Output is correct
3 Correct 375 ms 32488 KB Output is correct
4 Correct 377 ms 32792 KB Output is correct
5 Correct 359 ms 32660 KB Output is correct
6 Correct 190 ms 42412 KB Output is correct
7 Correct 330 ms 41952 KB Output is correct
8 Correct 327 ms 41956 KB Output is correct
9 Correct 552 ms 32656 KB Output is correct
10 Correct 546 ms 32708 KB Output is correct
11 Correct 192 ms 42440 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 25920 KB Output is correct
2 Correct 399 ms 30568 KB Output is correct
3 Correct 368 ms 32736 KB Output is correct
4 Correct 358 ms 32580 KB Output is correct
5 Correct 380 ms 32860 KB Output is correct
6 Correct 198 ms 42528 KB Output is correct
7 Correct 328 ms 41896 KB Output is correct
8 Correct 333 ms 41976 KB Output is correct
9 Correct 500 ms 32716 KB Output is correct
10 Correct 500 ms 32704 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 26244 KB Output is correct
2 Correct 402 ms 30468 KB Output is correct
3 Correct 377 ms 32612 KB Output is correct
4 Correct 381 ms 32820 KB Output is correct
5 Correct 373 ms 32752 KB Output is correct
6 Correct 337 ms 41828 KB Output is correct
7 Correct 325 ms 41976 KB Output is correct
8 Correct 464 ms 32676 KB Output is correct
9 Correct 477 ms 32712 KB Output is correct