Submission #1239764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239764		nikd	Seats (IOI18_seats)	C++20	0 / 100	153 ms	47412 KiB

seats

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

struct seg_min{
  int n; vector<int> t;
  void build(vector<int> &a){
    n = a.size(); t.resize(2*n);
    copy(a.begin(), a.end(), t.begin()+n);
    for(int i = n-1; i>0; i--) t[i] = min(t[i<<1],t[(i<<1)|1]);
    return;
  }
  void upd(int x, int i){
    for(t[i+=n] = x; i>>=1;) t[i] = min(t[i<<1], t[(i<<1)|1]);
    return;
  }
  int q(int l, int r){
    int sl = INT_MAX;
    for(l+=n, r+=n; l<=r; l>>=1, r>>=1){
      if(l&1) sl = min(sl, t[l++]);
      if(!(r&1)) sl = min(sl, t[r--]);
    }
    return sl;
  }
};

struct seg_max{
  int n; vector<int> t;
  void build(vector<int> &a){
    n = a.size(); t.resize(2*n);
    copy(a.begin(), a.end(), t.begin()+n);
    for(int i = n-1; i>0; i--) t[i] = max(t[i<<1],t[(i<<1)|1]);
    return;
  }
  void upd(int x, int i){
    for(t[i+=n] = x; i>>=1;) t[i] = max(t[i<<1], t[(i<<1)|1]);
    return;
  }
  int q(int l, int r){
    int sl = 0;
    for(l+=n, r+=n; l<=r; l>>=1, r>>=1){
      if(l&1) sl = max(sl, t[l++]);
      if(!(r&1)) sl = max(sl, t[r--]);
    }
    return sl;
  }
};

seg_min rn;
seg_max rx;
seg_min cn;
seg_max cx;
int h, w;


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  h = H; w = W;
  rn.build(R);
  rx.build(R);
  cn.build(C);
  cx.build(C);
  return;
}

int swap_seats(int a, int b) {
  int ca = cn.t[a+cn.n];
  int cb = cn.t[b+cn.n];
  int ra = rn.t[a+rn.n];
  int rb = rn.t[b+rn.n];
  cn.upd(cb, a);
  cx.upd(cb, a);
  cn.upd(ca, b);
  cx.upd(ca, b);
  rn.upd(rb, a);
  rx.upd(rb, a);
  rn.upd(ra, b);
  rx.upd(ra, b);
  auto get_rc = [&](int i)->int{
    return (cx.q(0, i)-cn.q(0, i)+1)*(rx.q(0,i)-rn.q(0, i)+1);
  };
  int sol = 0;
  for(int i = 0; i<h*w; i++){
    int sz = get_rc(i);
    i = sz-1;
    sol++;
  }
  return sol;
}

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