Submission #152756

#	Time	Username	Problem	Language	Result	Execution time	Memory
152756		Segtree	Seats (IOI18_seats)	C++14	Compilation error	0 ms	0 KiB

seats

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define N (1<<20)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
ll h,w,r[N],c[N],val[N];
namespace seg{
  ll mi[2*N],cnt[2*N],laz[2*N];
  void init(){
      for(int i=0;i<2*N;i++){
	  mi[i]=1e17,cnt[i]=1;
	  laz[i]=0;
      }
  }
  ll eval(ll k){
      if(k<N){
	  laz[k*2]+=laz[k];
	  laz[k*2+1]+=laz[k];
      }
      mi[k]+=laz[k]; laz[k]=0;
      return mi[k];
  }
  void upd(ll l,ll r,ll x){
      l+=N,r+=N;
      for(ll a=l,b=r;a<b;a>>=1,b>>=1){
	  if(a&1)laz[a++]+=x;
	  if(b&1)laz[--b]+=x;
      }
      for(ll a=l,b=r;a+b;a>>=1,b>>=1){
	  eval(a); eval(a^1);
	  if(mi[a]==mi[a^1])mi[a/2]=mi[a],cnt[a/2]=cnt[a]+cnt[a^1];
	  if(mi[a]<mi[a^1])mi[a/2]=mi[a],cnt[a/2]=cnt[a];
	  if(mi[a]>mi[a^1])mi[a/2]=mi[a^1],cnt[a/2]=cnt[a^1];
	  
	  eval(b); eval(b^1);
	  if(mi[b]==mi[b^1])mi[b/2]=mi[b],cnt[b/2]=cnt[b]+cnt[b^1];
	  if(mi[b]<mi[b^1])mi[b/2]=mi[b],cnt[b/2]=cnt[b];
	  if(mi[b]>mi[b^1])mi[b/2]=mi[b^1],cnt[b/2]=cnt[b^1];
      }
  }
  ll qry(ll l,ll r){
      l+=N,r+=N;
      for(ll d=20;~d;d--){
	  eval(l>>d);
	  eval(r>>d);
      }
      ll mii=1e17,cnts=0;
      for(ll a=l,b=r;a<b;a>>=1,b>>=1){
	  if(a&1){
	      if(mii==mi[a])cnts+=cnt[a];
	      if(mii>mi[a])mii=mi[a],cnts=cnt[a];
	      a++;
	  }
	  if(b&1){
	      b--;
	      if(mii==mi[b])cnts+=cnt[b];
	      if(mii>mi[b])mii=mi[b],cnts=cnt[b];
	  }
      }
      assert(mii>=2);
      if(mii>2)return 0;
      return cnts;
  }
  void outs(){
      for(int i=0;i<2*N;i++)eval(i);
      for(int a=2*N-1;a>0;a--){
	  if(mi[a]==mi[a^1])mi[a/2]=mi[a],cnt[a/2]=cnt[a]+cnt[a^1];
	  if(mi[a]<mi[a^1])mi[a/2]=mi[a],cnt[a/2]=cnt[a];
	  if(mi[a]>mi[a^1])mi[a/2]=mi[a^1],cnt[a/2]=cnt[a^1];
      }
      for(int i=0;i<N;i++){
	  //cout<<i<<":"<<mi[i+N]<<endl;
	  //assert(mi[i+N]>=2);
      }
  }
};
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
//void tapris(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    h=H,w=W;
    for(int i=0;i<h*w;i++)r[i]=R[i];
    for(int i=0;i<h*w;i++)c[i]=C[i];
    if(h==1){
    for(int i=0;i<w;i++){
	val[c[i]]=i;
    }
    seg::init();
    bool th[N];
    for(int i=0;i<=w+1;i++)th[i]=0;
    ll cnt=0;
    for(int i=0;i<w;i++){
	c[i]++;
	cnt+=(th[c[i]-1]==th[c[i]]?+1:-1);
	cnt+=(th[c[i]]==th[c[i]+1]?+1:-1);
	th[c[i]]=1;
	c[i]--;
	seg::mi[i+N]=cnt;
    }
    seg::outs();
    seg::qry(0,N-5);
    }
}
void func(ll x,ll kei){
    ll vl,vr,ma;
    vl=(c[x]==0?N-1:val[c[x]-1]);
    vr=(c[x]+1==w?N-1:val[c[x]+1]);
    ma=max(x,max(vl,vr));
    seg::upd(ma,N-1,kei*2);
    if(vl>x&&x<vr){
	seg::upd(x,min(vl,vr),kei*(-2));
    }
}
int swap_seats(int a,int b){
    if(h>1){
	swap(r[a],r[b]);
    swap(c[a],c[b]);
    ll xl=1e17,xr=-1e17,yl=1e17,yr=-1e17;
    ll ans=0;
    for(int k=0;k<h*w;k++){
	chmin(xl,r[k]);
	chmax(xr,r[k]);
	chmin(yl,c[k]);
	chmax(yr,c[k]);
	if((xr-xl+1)*(yr-yl+1)==k+1)ans++;
    }
    return ans;
    }
    func(a,+1);
    func(b,+1);
    swap(val[c[a]],val[c[b]]);
    swap(c[a],c[b]);
    func(a,-1);
    func(b,-1);
    return seg::qry(0,N-5);
}
/*
int main(){
  cin>>h>>w;
  for(int i=0;i<h*w;i++)cin>>r[i];
  for(int i=0;i<h*w;i++)cin>>c[i];
  tapris();
  while(1){
      ll a,b; cin>>a>>b;
      cout<<swap_seats(a,b)<<endl;
  }
  return 0;
}*/

Compilation message (stderr)

seats.cpp: In function 'll seg::qry(ll, ll)':
seats.cpp:65:7: error: 'assert' was not declared in this scope
       assert(mii>=2);
       ^~~~~~
seats.cpp:65:7: note: suggested alternative: 'qsort'
       assert(mii>=2);
       ^~~~~~
       qsort