Submission #152885

#	Time	Username	Problem	Language	Result	Execution time	Memory
152885		Segtree	Meetings (IOI18_meetings)	C++14	36 / 100	885 ms	12540 KiB

meetings

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define N (1<<17)
namespace seg{
  struct dat{
    ll L,R,M;  
    bool con;
  };  
  dat merge(dat a,dat b){
      dat c;
      if(a.con==1&&b.con==1){
	 c.L=a.L+b.L;
	 c.R=c.L;
	 c.M=c.L;
	 c.con=1;
	 return c; 
      }
      if(a.con==1){
	  c.L=a.L+b.L;
	  c.R=b.R;
	  c.M=max(max(c.L,c.R),max(a.M,b.M));
	  c.con=0;
	  return c;
      }
      if(b.con==1){
	  c.R=b.L+a.R;
	  c.L=a.L;
	  c.M=max(max(c.L,c.R),max(a.M,b.M));
	  c.con=0;
	  return c;
      }
      c.L=a.L,c.R=b.R;
      c.M=max(a.R+b.L,max(a.M,b.M));
      c.con=0;
      return c;
  }
  dat da[2*N],gen;
  void init(vector<int> H){
      gen.L=gen.R=gen.M=0;
      gen.con=0;
      for(int i=0;i<2*N;i++){
	  da[i]=gen;
      }
      for(int i=0;i<H.size();i++){
	if(H[i]==1){
	    da[i+N].L=1;
	    da[i+N].R=1;
	    da[i+N].con=1;
	    da[i+N].M=1;
	}  
	else{
	    da[i+N].L=0;
	    da[i+N].R=0;
	    da[i+N].con=0;
	    da[i+N].M=0;
	}
      }
      for(int i=N-1;i>0;i--){
	  da[i]=merge(da[i*2],da[i*2+1]);
      }
  }
  ll qry(ll l,ll r){
      l+=N,r+=N+1;
      vector<ll> s,t;
      for(ll a=l,b=r;a<b;a>>=1,b>>=1){
	  if(a&1)s.push_back(a++);
	  if(b&1)t.push_back(--b);
      }
      for(int i=t.size()-1;i>=0;i--){
	  s.push_back(t[i]);
      }
      dat res=da[s[0]];
      for(int i=1;i<s.size();i++){
	  res=merge(res,da[s[i]]);
      }
      return res.M;
  }
};
vector<ll> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
    vector<ll> anss;
    if(H.size()<=5010){
    for(int i=0;i<L.size();i++){
	ll res[5010];
	stack<pair<ll,ll> >s;
	ll sum=0;
	for(int k=L[i];k<=R[i];k++){
	    ll cnt=0;
	    while(!s.empty()&&s.top().first<=H[k]){
		cnt+=s.top().second;
		sum-=s.top().first*s.top().second;
		s.pop();
	    }
	    s.push(make_pair(H[k],cnt+1));
	    sum+=H[k]*(cnt+1);
	    res[k]=sum;
	}
	while(!s.empty()){
	    s.pop();
	}
	sum=0;
	for(int k=R[i];k>=L[i];k--){
	    ll cnt=0;
	    while(!s.empty()&&s.top().first<=H[k]){
		cnt+=s.top().second;
		sum-=s.top().first*s.top().second;
		s.pop();
	    }
	    s.push(make_pair(H[k],cnt+1));
	    sum+=H[k]*(cnt+1);
	    res[k]+=sum;
	}
	ll ans=1e17;
	for(int k=L[i];k<=R[i];k++){
	    ans=min(ans,res[k]-H[k]);
	}
	anss.push_back(ans);
    }
    }
    else{
	seg::init(H);
	for(int i=0;i<L.size();i++){
	    ll res=(R[i]-L[i]+1)*2;
	    res-=seg::qry(L[i],R[i]);
	    //cout<<seg::qry(L[i],R[i])<<endl;
	    //tap.push_back(seg::qry(L[i],R[i]));
	    anss.push_back(res);
	}
    }
    return anss;
}

Compilation message (stderr)

meetings.cpp: In function 'void seg::init(std::vector<int>)':
meetings.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<H.size();i++){
                   ~^~~~~~~~~
meetings.cpp: In function 'll seg::qry(ll, ll)':
meetings.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=1;i<s.size();i++){
                   ~^~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:87:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<L.size();i++){
                 ~^~~~~~~~~
meetings.cpp:126:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<L.size();i++){
              ~^~~~~~~~~

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