oj.uz

Submission #944953

# Submission time Handle Problem Language Result Execution time Memory
944953 2024-03-13T08:47:15 Z hmm789 Meetings (IOI18_meetings) C++14
0 / 100
 1387 ms 786432 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define int long long 

struct node {
	int s, e, m, v;
	node *l, *r;
	node(int _s, int _e) {
		s = _s, e = _e, m = (s+e)/2, v = 0;
		if(s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int x, int val) {
		if(s == e) {v = val; return;}
		else if(x > m) r->update(x, val);
		else l->update(x, val);
		v = l->v + r->v;
	}
	int rsum(int x, int y) {
		if(x <= s && e <= y) return v;
		else if(x > m) return r->rsum(x, y);
		else if(y <= m) return l->rsum(x, y);
		else return l->rsum(x, y) + r->rsum(x, y);
	}
} *root[5000];

struct node2 {
	int s, e, m, v;
	node2 *l, *r;
	node2(int _s, int _e) {
		s = _s, e = _e, m = (s+e)/2, v = 0;
		if(s != e) {
			l = new node2(s, m);
			r = new node2(m+1, e);
		}
	}
	void update(int x, int val) {
		if(s == e) {v = val; return;}
		else if(x > m) r->update(x, val);
		else l->update(x, val);
		v = max(l->v, r->v);
	}
	int rmax(int x, int y) {
		if(x <= s && e <= y) return v;
		else if(x > m) return r->rmax(x, y);
		else if(y <= m) return l->rmax(x, y);
		else return max(l->rmax(x, y), r->rmax(x, y));
	}
} *root2;
#undef int
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
	#define int long long
	int n = H.size(), q = L.size();
	root2 = new node2(0, n-1);
	for(int i = 0; i < n; i++) root2->update(i, H[i]);
	for(int i = 0; i < n; i++) {
		root[i] = new node(0, n-1);
		for(int j = 0; j < n; j++) root[i]->update(j, root2->rmax(min(i,j), max(i,j)));
	}
	vector<int> ans(q);
	for(int i = 0; i < q; i++) {
		int tmp = INF;
		for(int j = L[i]; j <= R[i]; j++) tmp = min(tmp, root[j]->rsum(L[i], R[i]));
		ans[i] = tmp;
	}
	return ans;
	#undef int
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1240 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1240 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1387 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1387 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 1240 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -