Submission #1208711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208711		QwertyPi	Seats (IOI18_seats)	C++20	5 / 100	4097 ms	86836 KiB

seats

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

int h,w,N;
vector<pair<int,int>> segm,segM,seats;

void build(int id,int l,int r){
  if(l==r){
    segm[id]=segM[id]=seats[l];
    return;
  }
  int m=l+(r-l)/2;
  build(2*id,l,m);
  build(2*id+1,m+1,r);
  segm[id].first=min(segm[id*2].first,segm[id*2+1].first);
  segm[id].second=min(segm[id*2].second,segm[id*2+1].second);
  segM[id].first=max(segM[id*2].first,segM[id*2+1].first);
  segM[id].second=max(segM[id*2].second,segM[id*2+1].second);
}

void update(int id,int l,int r,int &x,pair<int,int> &v){
  if(l==r){
    segm[id]=segM[id]=v;
    return;
  }
  int m=l+(r-l)/2;
  if(x<=m){
    update(id*2,l,m,x,v);
  }else{
    update(id*2+1,m+1,r,x,v);
  }
  segm[id].first=min(segm[id*2].first,segm[id*2+1].first);
  segm[id].second=min(segm[id*2].second,segm[id*2+1].second);
  segM[id].first=max(segM[id*2].first,segM[id*2+1].first);
  segM[id].second=max(segM[id*2].second,segM[id*2+1].second);
}

pair<int,int> querym(int id,int l,int r,int &R){
  if(l>R){
    return {1e9,1e9};
  }else if(r<=R){
    return segm[id];
  }
  int m=l+(r-l)/2;
  pair<int,int> ans=querym(id*2,l,m,R),tmp=querym(id*2+1,m+1,r,R);
  ans.first=min(ans.first,tmp.first);
  ans.second=min(ans.second,tmp.second);
  return ans;
}

pair<int,int> queryM(int id,int l,int r,int &R){
  if(l>R){
    return {-1,-1};
  }else if(r<=R){
    return segM[id];
  }
  int m=l+(r-l)/2;
  pair<int,int> ans=queryM(id*2,l,m,R),tmp=queryM(id*2+1,m+1,r,R);
  ans.first=max(ans.first,tmp.first);
  ans.second=max(ans.second,tmp.second);
  return ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  N=H*W;
  segm.resize(4*N);
  segM.resize(4*N);
  h=H;w=W;
  seats.resize(N+1);
  for(int i=0;i<N;i++){
    seats[i+1]={R[i],C[i]};
  }
  build(1,1,N);
}

int swap_seats(int a, int b) {
  int cnt=1,ans=0;a++;b++;
  update(1,1,N,a,seats[b]);
  update(1,1,N,b,seats[a]);
  swap(seats[a],seats[b]);
  int rnd = 0;
  while(cnt<=N){
    ++rnd;
    pair<int,int> m=querym(1,1,N,cnt),M=queryM(1,1,N,cnt);
    // cout << m.first << ' ' << m.second << ' ' << M.first << ' ' << M.second << '\n';
    int nxt;
    if((M.first-m.first+1)*(M.second-m.second+1)==cnt){
      ans++;
      nxt = cnt + min(M.first-m.first+1,M.second-m.second+1);
    }else{
      nxt = (M.first-m.first+1)*(M.second-m.second+1);
    }
    assert(nxt >= cnt);
    cnt = nxt;
  }
  return ans;
}

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