Submission #152736

#	Time	Username	Problem	Language	Result	Execution time	Memory
152736		Segtree	Seats (IOI18_seats)	C++14	0 / 100	868 ms	100984 KiB

seats

#include<bits/stdc++.h>
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]=0,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(){
      eval(1);
      //assert(mi[1]>=2);
      //cout<<"qry:"<<mi[1]<<" "<<cnt[1]<<endl;
      if(mi[1]==2)return cnt[1];
      return 0;
  }
  void outs(){
      for(int i=0;i<2*N;i++)eval(i);
      for(int i=0;i<N;i++){
	  //cout<<i<<":"<<mi[i+N]<<endl;
	  if(mi[i+N]==0){
	      upd(i,i+1,1e17);
	  }
	  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];
    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::upd(i,i+1,cnt);
    }
    for(int i=w;i<N;i++){
	seg::upd(i,i+1,1e17);
    }
    seg::outs();
}
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)return 0;
    func(a,+1);
    func(b,+1);
    swap(val[c[a]],val[c[b]]);
    swap(c[a],c[b]);
    func(a,-1);
    func(b,-1);
    //seg::outs();
    return seg::qry();
}
/*
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;
}*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30