Submission #1238567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238567		noyancanturk	Seats (IOI18_seats)	C++20	5 / 100	4094 ms	56796 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;

const int lim=1e6+100;

int n,h,w;

vector<int>r,c;

struct{
  int tree[4*lim];
  int P,VAL;
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=min(tree[child],tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  int L,R;
  int query(int l,int r,int node){
    if(L<=l&&r<=R)return tree[node];
    if(r<L||R<l)return INT_MAX;
    int mid=l+r>>1,child=node<<1;
    return min(query(l,mid,child),query(mid+1,r,child|1));
  }
  int query(int l,int r){
    L=l,R=r;
    return query(0,lim-1,1);
  }
}rmin,cmin;
struct{
  int tree[4*lim];
  int P,VAL;
  void update(int l,int r,int node){
    if(l==r){
      tree[node]=VAL;
      return;
    }
    int mid=l+r>>1,child=node<<1;
    if(P<=mid)update(l,mid,child);
    else update(mid+1,r,child|1);
    tree[node]=max(tree[child],tree[child|1]);
  }
  void update(int p,int val){
    P=p,VAL=val;
    update(0,lim-1,1);
  }
  int L,R;
  int query(int l,int r,int node){
    if(L<=l&&r<=R)return tree[node];
    if(r<L||R<l)return INT_MIN;
    int mid=l+r>>1,child=node<<1;
    return max(query(l,mid,child),query(mid+1,r,child|1));
  }
  int query(int l,int r){
    L=l,R=r;
    return query(0,lim-1,1);
  }
}rmax,cmax;

void updateguy(int i){
  cmax.update(i,c[i]);
  cmin.update(i,c[i]);
  rmax.update(i,r[i]);
  rmin.update(i,r[i]);
}

void give_initial_chart(int H,int W,vector<int>R,vector<int>C){
  n=H*W;
  h=H;
  w=W;
  r=R,c=C;
  for(int i=0;i<n;i++){
    updateguy(i);
  }
}

int swap_seats(int x,int y){
  swap(r[x],r[y]);
  swap(c[x],c[y]);
  updateguy(x);
  updateguy(y);
  // for(int i=0;i<n;i++){
  //   cerr<<c[i]<<' '<<r[i]<<' '<<cmax.query(i,i)<<' '<<cmin.query(i,i)<<' '<<rmax.query(i,i)<<' '<<rmin.query(i,i)<<'\n';
  // }
  int ans=0,mxc=INT_MIN,mxr=INT_MIN,mnr=INT_MAX,mnc=INT_MAX;
  int i=0;
  int rep=0;
  int prev=-1;
  while(i<n){
    mxc=cmax.query(0,i);
    mxr=rmax.query(0,i);
    mnc=cmin.query(0,i);
    mnr=rmin.query(0,i);
    int area=(mxc-mnc+1)*(mxr-mnr+1);
    // cerr<<i<<" :: "<<mxc<<' '<<mxr<<' '<<mnr<<' '<<mnc<<" :: "<<area<<'\n';;
    // assert(i+1<=area);
    if(i+1==area){
      ans++;
      i++;
    }else{
      i=area-1;
    }
    rep++;
    assert(rep<=3000);
    assert(i!=prev);
    prev=i;
  }
  return ans;
}

// std::vector<int> r;

// void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
//   r = R;
// }

// int swap_seats(int a, int b) {
//   return r[a];
// }

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