oj.uz

Submission #436756

# Submission time Handle Problem Language Result Execution time Memory
436756 2021-06-24T20:41:31 Z rqi Meetings (IOI18_meetings) C++14
41 / 100
 1196 ms 161164 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;
typedef vector<ll> vl;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define bk back()
#define ins insert

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const ll INF = 1e18;

void ckmax(int& a, int b){
	a = max(a, b);
}

void ckmin(ll& a, ll b){
	a = min(a, b);
}

const int MOD = 1e9+7;

const int mx = 100005;

mt19937 rng(127);

int N, Q;

struct Node{
	bool is_ID;
	array<ll, 21> meet_in_right;
	array<ll, 21> meet_in_left;
	array<ll, 21> meet_from_left;
	array<ll, 21> meet_from_right;
	int max_val;

	Node(){

	}

	Node(int val){
		if(val == -1){
			is_ID = 1;
		}
		else if(val == -2){ //use for comb
			is_ID = 0;
			for(int i = 1; i <= 20; i++){
				meet_in_right[i] = meet_in_left[i] = INF;
			}
		}
		else{
			is_ID = 0;
			max_val = val;
			for(int i = 1; i <= 20; i++){
				meet_in_right[i] = meet_in_left[i] = INF;
			}
			meet_in_right[val] = meet_in_left[val] = val;
			for(int i = 1; i <= 20; i++){
				meet_from_left[i] = meet_from_right[i] = max(i, val);
			}
		}
	}
};

void print(Node a){
	for(int i = 1; i <= 20; i++){
		cout << a.meet_in_right[i] << " " << a.meet_in_left[i] << "\n";
	}
}

Node comb(const Node& a, const Node& b){
	Node res = Node(-2);
	if(a.is_ID){
		res = b;
		return res;
	}
	if(b.is_ID){
		res = a;
		return res;
	}

	res.max_val = max(a.max_val, b.max_val);

	//compute res.meet_in_right
	
	for(int i = 1; i <= 20; i++){
		//consider left start
		ckmin(res.meet_in_right[max(i, b.max_val)], a.meet_in_right[i]+b.meet_from_left[i]);
		//consider right start
		ckmin(res.meet_in_right[i], a.meet_from_right[b.max_val]+b.meet_in_right[i]);
		ckmin(res.meet_in_right[b.max_val], a.meet_from_right[i]+b.meet_in_left[i]);
	}
	for(int i = 1; i <= 20; i++){
		//consider left start
		ckmin(res.meet_in_left[i], a.meet_in_left[i]+b.meet_from_left[a.max_val]);
		ckmin(res.meet_in_left[a.max_val], a.meet_in_right[i]+b.meet_from_left[i]);
		//consider right start
		ckmin(res.meet_in_left[max(a.max_val, i)], a.meet_from_right[i]+b.meet_in_left[i]);
	}

	for(int i = 1; i <= 20; i++){
		res.meet_from_left[i] = a.meet_from_left[i]+b.meet_from_left[max(i, a.max_val)];
		res.meet_from_right[i] = a.meet_from_right[max(i, b.max_val)]+b.meet_from_right[i];
	}
	

	return res;
}

const int SZ = 131072;
Node seg[2*SZ];

void pull(int ind){
	seg[ind] = comb(seg[2*ind], seg[2*ind+1]);
}

void build(){
	for(int i = SZ-1; i >= 1; i--){
		pull(i);
	}
}

Node query(int l, int r, int ind = 1, int L = 0, int R = SZ-1){
	if(r < L || R < l) return Node(-1);
	if(l <= L && R <= r){
		return seg[ind];
	}

	int M = (L+R)/2;
	return comb(query(l, r, 2*ind, L, M), query(l, r, 2*ind+1, M+1, R));
}

vl minimum_costs(vi H, vi L, vi R) {
	// cout << "HI" << "\n";
	// cout.flush();
	N = sz(H);
	Q = sz(L);

	for(int i = 0; i < N; i++){
		seg[SZ+i] = Node(H[i]);
	}
	build();

	// print(seg[SZ+0]);

	vl C(Q, INF);
	for(int i = 0; i < Q; i++){
		Node res = query(L[i], R[i]);
		for(int j = 1; j <= 20; j++){
			ckmin(C[i], res.meet_in_left[j]);
		}
	}	


	return C;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 88680 KB Output is correct
2 Correct 454 ms 95320 KB Output is correct
3 Correct 1000 ms 161164 KB Output is correct
4 Correct 1000 ms 161040 KB Output is correct
5 Correct 388 ms 161040 KB Output is correct
6 Correct 791 ms 161092 KB Output is correct
7 Correct 1030 ms 161144 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 88680 KB Output is correct
2 Correct 454 ms 95320 KB Output is correct
3 Correct 1000 ms 161164 KB Output is correct
4 Correct 1000 ms 161040 KB Output is correct
5 Correct 388 ms 161040 KB Output is correct
6 Correct 791 ms 161092 KB Output is correct
7 Correct 1030 ms 161144 KB Output is correct
8 Correct 1196 ms 161040 KB Output is correct
9 Correct 1161 ms 161092 KB Output is correct
10 Correct 898 ms 161024 KB Output is correct
11 Correct 1157 ms 161076 KB Output is correct
12 Correct 1119 ms 161048 KB Output is correct
13 Correct 894 ms 161052 KB Output is correct
14 Correct 1190 ms 161092 KB Output is correct
15 Correct 1079 ms 161112 KB Output is correct
16 Correct 1142 ms 161056 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -