oj.uz

Submission #139036

# Submission time Handle Problem Language Result Execution time Memory
139036 2019-07-31T08:24:27 Z ckodser Meetings (IOI18_meetings) C++14
36 / 100
 952 ms 5872 KB 
#include "meetings.h"
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e5+500;
const ll inf=1e18+900;
const ll mod=1e9+7;


vector<pii> vec;
ll rt[maxn];

ll seg[maxn*4];

void bild(ll l,ll r,ll node){
	if(l+1==r){
		seg[node]=rt[l];
		return;
	}
	ll mid=(l+r)/2;
	bild(l,mid,2*node);
	bild(mid,r,2*node+1);
	seg[node]=max(seg[2*node],seg[2*node+1]);
}
ll findMx(ll L,ll R,ll node,ll l,ll r){
	if(l<=L && R<=r){
		return seg[node];
	}
	if(r<=L || R<=l)return 0;
	ll mid=(L+R)/2;
	return max(findMx(L,mid,2*node,l,r),findMx(mid,R,2*node+1,l,r));
}
ll esht(pii a,pii b){
	pii c=mp(max(a.F,b.F),min(a.S,b.S));
	if(c.F<=c.S)return c.S-c.F+1;
	return 0;
}
ll findAns(ll l,ll r){
	ll x=lower_bound(vec.begin(),vec.end(),mp(l+1,(ll)0))-vec.begin()-1;
	ll ans=0;
	if(x>=0){
		ans=max(ans,esht(vec[x],mp(l,r)));
	}
	ll y=lower_bound(vec.begin(),vec.end(),mp(r+1,(ll)0))-vec.begin()-1;
	if(y>=0){
		ans=max(ans,esht(vec[y],mp(l,r)));
	}
	ans=max(ans,findMx(0,vec.size(),1,x+1,y));
	return ans;
}



vector<ll> solve(vector<int> h,vector<int> l,vector<int> r){
	vector<ll> anS(l.size());
	ll n=h.size();
	ll q=l.size();
	for(ll i=0;i<n;i++){
		if(h[i]==1){
			if(vec.empty()){
				vec.pb(mp(i,i));
			}else{
				if(vec.back().S==i-1){
					vec.back().S=i;
				}else{
					vec.pb(mp(i,i));
				}
			}
		}	
	}
	for(ll i=0;i<vec.size();i++){
		rt[i]=vec[i].S-vec[i].F+1;
	}
	bild(0,vec.size(),1);
	for(ll i=0;i<q;i++){
		anS[i]=2*(r[i]-l[i]+1)-findAns(l[i],r[i]);
	}
	return anS;
}






ll tmp[maxn];
vector<ll> easy(vector<int> h,vector<int> l,vector<int> r){
	vector<ll> anS(l.size());
	ll n=h.size();
	ll q=l.size();
	for(ll i=0;i<q;i++){
		stack<ll> stk;
		stk.push(l[i]);
		ll res=h[l[i]];
		tmp[l[i]]=res;
		for(ll j=l[i]+1;j<=r[i];j++){
			res+=h[j];
			while(stk.size() && h[stk.top()]<=h[j]){
				ll v=stk.top();
				stk.pop();
				ll f;
				if(stk.empty()){
					f=l[i];
				}else{
					f=stk.top()+1;
				}
				res+=(h[j]-h[v])*(v-f+1);
			}
			stk.push(j);
			tmp[j]=res;
		}
		while(stk.size())stk.pop();
		stk.push(r[i]);
		res=h[r[i]];
		tmp[r[i]]+=res;
		for(ll j=r[i]-1;j>=l[i];j--){
			res+=h[j];
			while(stk.size() && h[stk.top()]<=h[j]){
				ll v=stk.top();
				stk.pop();
				ll f;
				if(stk.empty()){
					f=r[i];
				}else{
					f=stk.top()-1;
				}
				res+=(h[j]-h[v])*(f-v+1);
			}
			stk.push(j);
			tmp[j]+=res;
		}
		while(stk.size())stk.pop();



		ll ans=inf;
		for(ll j=l[i];j<=r[i];j++){
			ans=min(ans,tmp[j]-h[j]);
			tmp[j]=0;
		}
		anS[i]=ans;
	}
	return anS;
}
vector<long long> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
	if(H.size()<=5000 && L.size()<=5000){
		return easy(H,L,R);
	}
	ll mx=0;
	for(auto y:H){
		mx=max(mx,(ll)y);
	}
	if(mx>2 || H.size()>maxn || L.size()>maxn){
		exit(1);
	}
	return solve(H,L,R);
}

Compilation message

meetings.cpp: In function 'std::vector<long long int> solve(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:80:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i=0;i<vec.size();i++){
             ~^~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> easy(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:98:5: warning: unused variable 'n' [-Wunused-variable]
  ll n=h.size();
     ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 314 ms 624 KB Output is correct
11 Correct 952 ms 616 KB Output is correct
12 Correct 312 ms 620 KB Output is correct
13 Correct 945 ms 632 KB Output is correct
14 Correct 178 ms 616 KB Output is correct
15 Correct 191 ms 632 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 43 ms 2040 KB Output is correct
3 Correct 125 ms 5848 KB Output is correct
4 Correct 85 ms 4624 KB Output is correct
5 Correct 105 ms 5872 KB Output is correct
6 Correct 67 ms 4728 KB Output is correct
7 Correct 62 ms 4612 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 43 ms 2040 KB Output is correct
3 Correct 125 ms 5848 KB Output is correct
4 Correct 85 ms 4624 KB Output is correct
5 Correct 105 ms 5872 KB Output is correct
6 Correct 67 ms 4728 KB Output is correct
7 Correct 62 ms 4612 KB Output is correct
8 Runtime error 46 ms 2712 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 314 ms 624 KB Output is correct
11 Correct 952 ms 616 KB Output is correct
12 Correct 312 ms 620 KB Output is correct
13 Correct 945 ms 632 KB Output is correct
14 Correct 178 ms 616 KB Output is correct
15 Correct 191 ms 632 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 43 ms 2040 KB Output is correct
18 Correct 125 ms 5848 KB Output is correct
19 Correct 85 ms 4624 KB Output is correct
20 Correct 105 ms 5872 KB Output is correct
21 Correct 67 ms 4728 KB Output is correct
22 Correct 62 ms 4612 KB Output is correct
23 Runtime error 46 ms 2712 KB Execution failed because the return code was nonzero
24 Halted 0 ms 0 KB -