제출 #1111878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111878		epicci23	모임들 (IOI18_meetings)	C++17	36 / 100	591 ms	395008 KiB

meetings

#include "bits/stdc++.h"
#include "meetings.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll INF = 1e18;
const ll N = 1e6 + 5;

ll ar[N];
array<ll,4> seg[4*N];

array<ll,4> merge(array<ll,4> a,array<ll,4> b){
  if(a[0]==-1) return b;
  if(b[0]==-1) return a;
  array<ll,4> res;
  res[3]=a[3]+b[3];

  res[0]=max(a[0],b[0]);  
  res[0]=max(res[0],a[2]+b[1]);
  
  res[2]=b[2];
  if(b[0]==b[3]) res[2]=max(res[2],b[0]+a[2]);
  res[1]=a[1];
  if(a[0]==a[3]) res[1]=max(res[1],a[0]+b[1]);


  res[0]=max(res[0],res[1]);
  res[0]=max(res[0],res[2]);
  return res;
}

void build(ll rt,ll l,ll r){
  if(l==r){
  	seg[rt]={0,0,0,1};
  	if(ar[l]==1) seg[rt]={1,1,1,1};
  	return;
  }
  ll m = (l+r)/2;
  build(rt*2,l,m),build(rt*2+1,m+1,r);
  seg[rt]=merge(seg[rt*2],seg[rt*2+1]);
}

array<ll,4> query(ll rt,ll l,ll r,ll gl,ll gr){
  if(r<gl || l>gr) return {-1LL,-1LL,-1LL,-1LL};
  if(l>=gl && r<=gr) return seg[rt];
  ll m=(l+r)/2;
  return merge(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R){
  ll n,q;
  n=sz(H),q=sz(L);
  vector<ll> res;
  for(int i=1;i<=n;i++) ar[i]=H[i-1];
  
  if(n<=5005){
	  ll mx[n+5][n+5];

	  for(int i=1;i<=n;i++){
	  	ll hm = ar[i];
	  	for(int j=i;j<=n;j++){
	      hm=max(hm,ar[j]);
	      mx[i][j]=hm;
	  	}
	  }

	  ll pre[n+5][n+5];
	  memset(pre,0,sizeof(pre));
	  for(int i=1;i<=n;i++){
	  	ll cur = 0;
	  	for(int j=i;j<=n;j++){
	  	  cur += mx[i][j];
	      pre[i][j] = cur;
	  	}
	  	cur = 0;
	  	for(int j=i;j>=1;j--){
	      cur += mx[j][i];
	      pre[i][j] = cur;
	  	}
	  }
	  
	  
	  for(int i=0;i<q;i++){
	  	ll l,r;
	  	l=L[i]+1,r=R[i]+1;
	  	ll xd = INF;
	  	for(int i=l;i<=r;i++){
	  	  ll curi = pre[i][l] + pre[i][r] - ar[i];
	  	  xd = min(xd, curi);
	  	}
	  	res.push_back(xd);
	  }
  }
  else{
    build(1,1,n);
    for(int i=0;i<q;i++){
      ll l = L[i]+1 , r = R[i] + 1;
      auto u = query(1,1,n,l,r);
      res.push_back(2LL*(r-l+1LL) - u[0]);
    }
  }

  return res;
}



/*void _(){
  int n,q;
  cin >> n >> q;

  int ar[n+5];
  for(int i=1;i<=n;i++) cin >> ar[i];
  int mx[n+5][n+5];

  for(int i=1;i<=n;i++){
  	int hm = ar[i];
  	for(int j=i;j<=n;j++){
      hm=max(hm,ar[j]);
      mx[i][j]=hm;
  	}
  }

  int pre[n+5][n+5];
  memset(pre,0,sizeof(pre));
  for(int i=1;i<=n;i++){
  	int cur = 0;
  	for(int j=i;j<=n;j++){
  	  cur += mx[i][j];
      pre[i][j] = cur;
  	}
  	cur = 0;
  	for(int j=i;j>=1;j--){
      cur += mx[j][i];
      pre[i][j] = cur;
  	}
  }

  while(q--){
  	int l,r;
  	cin >> l >> r;
  	int res = INF;
  	for(int i=l;i<=r;i++){
  	  int curi = pre[i][l] + pre[i][r] - ar[i];
  	  res = min(res, curi);
  	}
  	cout << res << '\n';
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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