oj.uz

Submission #598484

# Submission time Handle Problem Language Result Execution time Memory
598484 2022-07-18T11:53:21 Z imtore 수족관 3 (KOI13_aqua3) C++14
48 / 100
 78 ms 10644 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)+(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 0 ms 212 KB Output is correct
2 Correct 0 ms 296 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 428 KB Output is correct
2 Correct 2 ms 432 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 552 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 428 KB Output is correct
10 Correct 2 ms 496 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 10560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 10544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 10644 KB Output isn't correct
2 Halted 0 ms 0 KB -