제출 #1290251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290251		ackhava	자리 배치 (IOI18_seats)	C++20	0 / 100	4099 ms	86560 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;

std::vector<int> r;

struct segment_tree{
  vector<pair<pair<int,int>,pair<int,int>>> vec;

  pair<pair<int,int>,pair<int,int>> e = {{1e8,-1}, {1e8,-1}};

  pair<pair<int,int>,pair<int,int>> merge(pair<pair<int,int>,pair<int,int>> a, pair<pair<int,int>,pair<int,int>> b){
    return {{min(a.fi.fi,b.fi.fi), max(a.fi.se,b.fi.se)},{min(a.se.fi,b.se.fi), max(a.se.se,b.se.se)}};
  }

  void update(int pos, int l, int r, int q, pair<int,int> v){
    if(r < q)return;
    if(l > q)return;
    if(l==r){
      vec[pos] = {{v.fi,v.fi},{v.se,v.se}};
      return;
    }
    int m = (l+r)/2;
    update(pos*2+1,l,m,q,v);
    update(pos*2+2,m+1,r,q,v);
    vec[pos] = merge(vec[pos*2+1],vec[pos*2+2]);
  }

  pair<pair<int,int>,pair<int,int>> query(int pos, int l, int r, int ql, int qr){
    if(r < ql)return e;
    if(l > qr)return e;
    if(ql <= l && r <= qr)return vec[pos];
    int m = (l+r)/2;
    return merge(query(pos*2+1,l,m,ql,qr),query(pos*2+2,m+1,r,ql,qr));
  }
};

segment_tree segtree;
vector<int> R,C;
int H,W;
int N;
set<int> valid;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  ::R=R;
  ::C=C;
  ::H=H;
  ::W=W;
  ::N=H*W;
  segtree.vec.resize(4*N+100, segtree.e);
  for(int i=0;i<(N);i++){
    segtree.update(0,0,N,i,{R[i],C[i]});
    auto res = segtree.query(0,0,N,0,i);
    // cerr<<i<<": "<<res.fi.fi<<" "<<res.fi.se<<" "<<res.se.fi<<" "<<res.se.se<<"\n";
    if(((res.fi.se-res.fi.fi+1)*(res.se.se-res.se.fi+1)) == (i+1)){
      valid.insert(i);
    }
  }
}

int swap_seats(int a, int b) {
  while(valid.lower_bound(a) != valid.upper_bound(b))valid.erase(valid.lower_bound(a));
  swap(R[a],R[b]);
  swap(C[a],C[b]);
  for(int i=a;i<=b;i++){
    segtree.update(0,0,N,i,{R[i],C[i]});
    auto res = segtree.query(0,0,N,0,i);
    if(((res.fi.se-res.fi.fi+1)*(res.se.se-res.se.fi+1)) == (i+1)){
      valid.insert(i);
    }
  }
  return valid.size();
}

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