Submission #152719

#	Time	Username	Problem	Language	Result	Execution time	Memory
152719		Segtree	Seats (IOI18_seats)	C++14	0 / 100	368 ms	84940 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]=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);
      if(mi[1]==2)return cnt[1];
      return 0;
  }
};
void give_initial_chart(int H,int W,vector<int> R,vector<int> C){
    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;i++)th[i]=0;
    ll cnt=0;
    for(int i=0;i<W;i++){
	if(c[i]>0)cnt+=(th[i-1]==th[i]?-1:+1);
	if(c[i]+1<W)cnt+=(th[i]==th[i+1]?-1:+1);
	seg::upd(i,i,cnt);
    }
}
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);
    return seg::qry();
}/*
int main(){
  
  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