Submission #436456

#	Time	Username	Problem	Language	Result	Execution time	Memory
436456		rqi	Meetings (IOI18_meetings)	C++14	36 / 100	3388 ms	204544 KiB

meetings

#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 BIT{
	ll BT[5005];
	void upd(int pos, ll val){
		pos++;
		for(int i = pos; i < 5005; i+=i&-i){
			// cout << i << "\n";
			// cout.flush();
			BT[i]+=val;
		}
	}

	ll sum(int pos){
		ll res = 0;
		for(int i = pos; i > 0; i-=i&-i){
			// cout << i << "\n";
			// cout.flush();
			res+=BT[i];
		}
		return res;
	}

	ll query(int l, int r){
		l++;
		r++;
		return sum(r)-sum(l-1);
	}
};

BIT bt[5005];

struct Node{
	int max_rang, max_pre, max_suf;
	bool whole_range;

	Node(){
		max_rang = max_pre = max_suf = 0;
		whole_range = 0;
	}

	Node(int val){
		assert(1 <= val && val <= 2);
		if(val == 1){
			max_rang = max_pre = max_suf = 1;
			whole_range = 1;
		}
		else{
			max_rang = max_pre = max_suf = 0;
			whole_range = 0;
		}
	}
};

Node comb(const Node& a, const Node& b){
	Node c = Node(2);
	c.whole_range = a.whole_range & b.whole_range;
	c.max_rang = max(a.max_rang, b.max_rang);
	c.max_pre = a.max_pre;
	c.max_suf = b.max_suf;
	if(a.whole_range){
		ckmax(c.max_pre, a.max_pre+b.max_pre);
	}
	if(b.whole_range){
		ckmax(c.max_suf, a.max_suf+b.max_suf);
	}
	ckmax(c.max_rang, a.max_suf+b.max_pre);

	return c;
}

const int SZ = 262144;
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(2);
	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);

	if(N <= 5000 && Q <= 5000){
		for(int i = 0; i < N; i++){
			bt[i].upd(i, H[i]);
			int cur_max = H[i];
			for(int j = i-1; j >= 0; j--){
				ckmax(cur_max, H[j]);
				bt[i].upd(j, cur_max);
			}
			cur_max = H[i];
			for(int j = i+1; j < N; j++){
				ckmax(cur_max, H[j]);
				bt[i].upd(j, cur_max);

				// cout << "building: " << i << " " << j << " " << cur_max << "\n";
			}
		}

		// for(int i = 0; i < N; i++){
		// 	for(int j = 0; j < N; j++){
		// 		cout << i << " " << j << " " << bt[i].query(j, j) << "\n";
		// 	}
		// }

		vl C(Q, INF);
		for(int i = 0; i < Q; i++){
			ll ans = INF;
			for(int j = L[i]; j <= R[i]; j++){
				ckmin(ans, bt[j].query(L[i], R[i]));
			}
			C[i] = ans;
		}
		return C;
	}

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

	vl C(Q, 0);
	for(int i = 0; i < Q; i++){
		C[i] = query(L[i], R[i]).max_rang;
		C[i] = 2*(R[i]-L[i]+1)-C[i];
	}
		
	return C;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40