Submission #360580

#	Time	Username	Problem	Language	Result	Execution time	Memory
360580		tengiz05	Meetings (IOI18_meetings)	C++17	17 / 100	100 ms	10144 KiB

meetings

#include "meetings.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+5;
int n;
struct node{
	ll pr, sf, ans, sz;
}t[MAXN*2];
node merge(node &l, node &r){
	node res = {0,0,0,l.sz + r.sz};
	if(l.pr == l.sz)res.pr = l.sz + r.pr;
	else res.pr = l.pr;
	if(r.sf == r.sz)res.sf = r.sz + l.sf;
	else res.sf = r.sf;
	res.ans = max(l.sf + r.pr, max(res.pr, res.sf));
	res.ans = max({res.ans, l.ans, r.ans});
	return res;
}
int query(int l,int r){
	node resl = {0,0,0,0}, resr = {0,0,0,0};
	for(l+=n,r+=n; l<=r; l>>=1,r>>=1){
		if(l&1)resl = merge(resl, t[l++]);
		if(!(r&1))resr=merge(t[r--],resr);
	}return merge(resl,resr).ans;
}
vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R){
	n = h.size();
	int Q = L.size();
	for(int i=0;i<n;i++){
		if(h[i] == 1)t[i+n] = {1,1,1,1};
		else t[i+n] = {0,0,0,1};
	}for(int i=n-1;i>0;i--)t[i] = merge(t[i<<1],t[i<<1|1]);
	vector<ll> ret;
	for(int q=0;q<Q;q++){
		ll l = L[q], r = R[q];
		ll res = query(l,r);
		assert(res <= r-l+1);
		res += (r-l+1-res)*2ll;
		ret.push_back(res);
	}return ret;
}

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