oj.uz

Submission #598486

# Submission time Handle Problem Language Result Execution time Memory
598486 2022-07-18T11:53:56 Z imtore 수족관 3 (KOI13_aqua3) C++14
100 / 100
 117 ms 25268 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
#define INF (int)1e9
using namespace std;

vector<int> X, Y;
priority_queue<LL> pq;

struct Indexed_Tree{
	int bias;
	vector<pii> tree;

	void init(int n){
		for(bias = 1; bias < n; bias <<= 1);
		tree.resize(bias<<1);

		for(int i = 0; i < n; i++) tree[i|bias] = {Y[i+1], i};
		for(int i = n; i < bias; i++) tree[i|bias] = {INF, INF};
		for(int i = bias-1; i; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
	}

	pii query_min(int s, int e){
		pii mn = {INF, INF};
		s |= bias; e |= bias;
		while(s <= e){
			if(s&1) mn = min(mn, tree[s++]);
			if(~e&1) mn = min(mn, tree[e--]);
			s >>= 1; e >>= 1;
		}
		return mn;
	}
}IDT;

LL dfs(int s, int e, int y){
	if(s == e) return 0;

	//printf("%d %d %d\n", s, e, y);

	pii mn = IDT.query_min(s, e-1);
	//printf("%d %d\n", mn.ff, mn.ss);
	LL res1 = dfs(s, mn.ss, mn.ff);
	LL res2 = dfs(mn.ss+1, e, mn.ff);
	pq.push(min(res1, res2));
	
	return max(res1, res2)+(LL)(X[e]-X[s])*(mn.ff-y);
}

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

	IDT.init(X.size()-1);

	//for(int i = 1; i < (IDT.bias<<1); i++) printf("%d : %d %d\n", i, IDT.tree[i].ff, IDT.tree[i].ss);

	pq.push(dfs(0, X.size()-1, 0));

	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:59:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
aqua3.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   int x, y; scanf("%d %d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~~
aqua3.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d", &k);
      |  ~~~~~^~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 472 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 5820 KB Output is correct
2 Correct 67 ms 9624 KB Output is correct
3 Correct 84 ms 15880 KB Output is correct
4 Correct 95 ms 15868 KB Output is correct
5 Correct 90 ms 15880 KB Output is correct
6 Correct 96 ms 25136 KB Output is correct
7 Correct 91 ms 19344 KB Output is correct
8 Correct 113 ms 19376 KB Output is correct
9 Correct 83 ms 13436 KB Output is correct
10 Correct 87 ms 13444 KB Output is correct
11 Correct 117 ms 25268 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5828 KB Output is correct
2 Correct 69 ms 9608 KB Output is correct
3 Correct 87 ms 15844 KB Output is correct
4 Correct 92 ms 15864 KB Output is correct
5 Correct 105 ms 15840 KB Output is correct
6 Correct 102 ms 25184 KB Output is correct
7 Correct 94 ms 19372 KB Output is correct
8 Correct 89 ms 19148 KB Output is correct
9 Correct 95 ms 13352 KB Output is correct
10 Correct 103 ms 13404 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5940 KB Output is correct
2 Correct 76 ms 9280 KB Output is correct
3 Correct 97 ms 15480 KB Output is correct
4 Correct 89 ms 15304 KB Output is correct
5 Correct 95 ms 15460 KB Output is correct
6 Correct 112 ms 18568 KB Output is correct
7 Correct 102 ms 18680 KB Output is correct
8 Correct 88 ms 12692 KB Output is correct
9 Correct 93 ms 12632 KB Output is correct