oj.uz

Submission #944960

# Submission time Handle Problem Language Result Execution time Memory
944960 2024-03-13T08:58:28 Z hmm789 Meetings (IOI18_meetings) C++14
19 / 100
 3190 ms 401416 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define int long long 

int fw[5000][5005];

void update(int i, int x, int v) {
	for(x++; x < 5005; x += x&-x) fw[i][x] += v;
}
int query(int i, int x) {
	int ans = 0;
	for(x++; x; x -= x&-x) ans += fw[i][x];
	return ans;
}
int query(int i, int x, int y) {
	return query(i, y) - query(i, x-1);
}

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++) {
		for(int j = 0; j < n; j++) update(i, 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, query(j, L[i], R[i]));
		ans[i] = tmp;
	}
	return ans;
	#undef int
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 686 ms 119752 KB Output is correct
3 Correct 670 ms 120080 KB Output is correct
4 Correct 671 ms 119892 KB Output is correct
5 Correct 663 ms 120004 KB Output is correct
6 Correct 679 ms 119892 KB Output is correct
7 Correct 663 ms 119952 KB Output is correct
8 Correct 667 ms 119920 KB Output is correct
9 Correct 666 ms 119936 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 686 ms 119752 KB Output is correct
3 Correct 670 ms 120080 KB Output is correct
4 Correct 671 ms 119892 KB Output is correct
5 Correct 663 ms 120004 KB Output is correct
6 Correct 679 ms 119892 KB Output is correct
7 Correct 663 ms 119952 KB Output is correct
8 Correct 667 ms 119920 KB Output is correct
9 Correct 666 ms 119936 KB Output is correct
10 Correct 2510 ms 197092 KB Output is correct
11 Correct 2507 ms 196944 KB Output is correct
12 Correct 2532 ms 197080 KB Output is correct
13 Correct 2665 ms 197112 KB Output is correct
14 Correct 2533 ms 197472 KB Output is correct
15 Correct 2566 ms 197276 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 3190 ms 401416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Runtime error 3190 ms 401416 KB Execution killed with signal 11
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 Correct 686 ms 119752 KB Output is correct
3 Correct 670 ms 120080 KB Output is correct
4 Correct 671 ms 119892 KB Output is correct
5 Correct 663 ms 120004 KB Output is correct
6 Correct 679 ms 119892 KB Output is correct
7 Correct 663 ms 119952 KB Output is correct
8 Correct 667 ms 119920 KB Output is correct
9 Correct 666 ms 119936 KB Output is correct
10 Correct 2510 ms 197092 KB Output is correct
11 Correct 2507 ms 196944 KB Output is correct
12 Correct 2532 ms 197080 KB Output is correct
13 Correct 2665 ms 197112 KB Output is correct
14 Correct 2533 ms 197472 KB Output is correct
15 Correct 2566 ms 197276 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Runtime error 3190 ms 401416 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -