Submission #295830

#	Time	Username	Problem	Language	Result	Execution time	Memory
295830		Gurban	Meetings (IOI18_meetings)	C++17	36 / 100	5616 ms	538396 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define mkp make_pair
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 1e5+5,N=1e6;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int T[4*N];
ll p[maxn];
ll jog[maxn];
stack<pii>s;
vector<pii> v;

void upd(int pos,int val,int l,int r,int nd){
	if(l==r){
		T[nd] = val;
		return;
	}

	if(pos <= (l+r)/2) upd(pos,val,l,(l+r)/2,nd*2);
	else upd(pos,val,(l+r)/2+1,r,nd*2+1);
	
	T[nd] = max(T[nd*2],T[nd*2+1]);
}

int tap(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return 0;
	if(l >= a and r <= b) return T[nd];
	return max(tap(a,b,l,(l+r)/2,nd*2),tap(a,b,(l+r)/2+1,r,nd*2+1));
}

vll minimum_costs(vi H, vi L,vi R) {
	int Q=sz(L); vll C;
	if(Q<1e4){
		int cep[maxn],sag[maxn];
		memset(cep,0,sizeof(cep));
		memset(sag,0,sizeof(sag));
		for(int i = 0;i < Q;i++){
			
			memset(jog,0,sizeof(jog));
			memset(cep,0,sizeof(cep));
			memset(sag,0,sizeof(sag));
			memset(p,0,sizeof(p));

			while(!s.empty()) s.pop();

			for(int j = L[i];j <= R[i];j++){
				while(!s.empty() and s.top().ss <= H[j]) s.pop();
				if(!s.empty()) cep[j]=s.top().ff+1;	
				else cep[j]=L[i];
				s.push({j,H[j]});
			}
			
			while(!s.empty()) s.pop();
			
			for(int j = R[i];j >= L[i];j--){
				while(!s.empty() and s.top().ss < H[j]) s.pop();
				if(!s.empty()) sag[j]=s.top().ff-1;
				else sag[j]=R[i];
				s.push({j,H[j]});
			}
			for(int j = L[i];j <= R[i];j++){
				ll num=j-cep[j];
				ll num1= sag[j]-j;
				p[cep[j]] += ((num1+1)*H[j]);
				p[j] -= ((num1+1)*H[j]);
				p[j+1] += ((num+1)*H[j]);
				p[sag[j]+1] -= ((num+1)*H[j]);
				jog[j] = (num+num1+1)*H[j];
			}
			ll ans = inf;
			for(int j = L[i];j <= R[i];j++){
				if(j) p[j] += p[j-1];
				ans = min(ans,p[j]+jog[j]);
			}	
			C.pb(ans);
		}
		return C;
	}
	else {
		int n = sz(H);
		int cep[N],sag[N];
		memset(cep,-1,sizeof(cep));
		memset(sag,-1,sizeof(sag));
		for(int i = 0;i < n;i++){
			if(H[i]==2) continue;
			if(i==0) cep[0]=0;
			else {
				if(H[i-1]==1) cep[i]=cep[i-1];
				else cep[i]=i;
			}
		}
		for(int i = n-1;i >= 0;i--){
			if(H[i]==2) continue;
			if(i == n-1) sag[i]=i;
			else {
				if(H[i+1]==1) sag[i] = sag[i+1];
				else sag[i] = i;
			}
		}
		for(int i = 0;i < n;i++){
			if(H[i]==2) continue;
			int now = i;
			while(H[now]==1) now++;
			v.pb({i,now-i});
			upd(i,now-i,0,n-1,1);
			i = now-1;
		}

		int ans;
		for(int i = 0;i < Q;i++){
			ans = 0;
			int siz = R[i] - L[i] + 1;
			if(sag[L[i]] != -1 and sag[L[i]] >= R[i]){
				C.pb(siz);
				continue;
			}
			if(H[L[i]]==1) ans = max(ans,sag[L[i]]-L[i]+1),L[i] = sag[L[i]]+1;																																																																																	
			if(H[R[i]]==1) ans = max(ans,R[i]-cep[R[i]]+1),R[i] = cep[R[i]]-1;

			ans=max(ans,tap(L[i],R[i],0,n-1,1));

			C.pb(2*siz-ans);
		}
		return C;
	}
}

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