제출 #772856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772856		I_Love_EliskaM_	자리 배치 (IOI18_seats)	C++14	37 / 100	4062 ms	76564 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9;

vector<int> r, c;
int n,m;

struct sgt {
  vector<pi> mn,mx; int sz=1;
  sgt(int n) {
    while (sz<n) sz<<=1;
    mn.assign(2*sz-1,{inf,inf});
    mx.assign(2*sz-1,{-inf,-inf});
  }
  void upd(int v, int l, int r, int i) {
    if (r-l==1) return;
    int m=(l+r)>>1;
    if (i<m) upd(2*v+1,l,m,i);
    else upd(2*v+2,m,r,i);
    mn[v].f=min(mn[2*v+1].f,mn[2*v+2].f);
    mn[v].s=min(mn[2*v+1].s,mn[2*v+2].s);
    mx[v].f=max(mx[2*v+1].f,mx[2*v+2].f);
    mx[v].s=max(mx[2*v+1].s,mx[2*v+2].s);
  }
  void set(int i, pi x) {
    mn[sz-1+i]=mx[sz-1+i]=x;
    upd(0,0,sz,i);
  }

  pair<pi,pi> query(int v, int l, int r, int lx, int rx) {
    if (rx<=l || r<=lx) return {{inf,inf},{-inf,-inf}};
    if (lx<=l && r<=rx) return {mn[v],mx[v]};
    int m=(l+r)>>1;
    auto lq = query(2*v+1,l,m,lx,rx);
    auto rq = query(2*v+2,m,r,lx,rx);
    return { {min(lq.f.f,rq.f.f),min(lq.f.s,rq.f.s)} , {max(lq.s.f,rq.s.f),max(lq.s.s,rq.s.s)} };
  }
  pair<pi,pi> query(int l, int r) {
    return query(0,0,sz,l,r);
  }
};
sgt st(1e6);
int z=0;
const int N=1e6;
int ok[N];
int lz[N];
int rz[N];
int uz[N];
int dz[N];

void give_initial_chart(int N, int M, vector<int> R, vector<int> C) {
  r=R, c=C;
  n=N, m=M;
  forn(i,n*m) st.set(i,{r[i],c[i]});
  int lx=m-1, rx=0, u=n-1, d=0;
  forn(i,n*m) {
    lx=min(lx,c[i]), rx=max(rx,c[i]);
    u=min(u,r[i]), d=max(d,r[i]);
    z += (rx-lx+1)*(d-u+1) == (i+1);
    if ( (rx-lx+1)*(d-u+1) == (i+1) ) ok[i]=1;
    lz[i]=lx, rz[i]=rx, uz[i]=u, dz[i]=d;
  }
}

int I_Love_EliskaM_ = true;
int I_Am_Stupid = 1;

int swap_seats(int x, int y) {
  swap(r[x],r[y]);
  swap(c[x],c[y]);
  st.set(x,{r[x],c[x]});
  st.set(y,{r[y],c[y]});

  if (n*m<=1e4) {
      int ans=0;
      int lx=m-1, rx=0, u=n-1, d=0;
      forn(i,n*m) {
        lx=min(lx,c[i]), rx=max(rx,c[i]);
        u=min(u,r[i]), d=max(d,r[i]);
        ans += (rx-lx+1)*(d-u+1) == (i+1);
      }
      return ans;
  }
  if (x>y) swap(x,y);
  if (y-x<=10000 && I_Am_Stupid) {

    int lx,rx,ux,dx;
    if (x) {
      lx=lz[x-1], rx=rz[x-1], ux=uz[x-1], dx=dz[x-1];
    } else {
      lx=m-1, rx=0, ux=n-1, dx=0;
    }
    for (int i=x; i<=y; ++i) {
      z-=ok[i]; ok[i]=0;
      lx=min(lx,c[i]), rx=max(rx,c[i]);
      ux=min(ux,r[i]), dx=max(dx,r[i]);
      lz[i]=lx, rz[i]=rx, uz[i]=ux, dz[i]=dx;
      ok[i] = (rx-lx+1)*(dx-ux+1) == (i+1);
      z+=ok[i];
    }
    return z;

  } else I_Am_Stupid=0;

  int ans=0;
  int i=1;
  while (i<=n*m) {
    auto q = st.query(0,i);
    int u = q.f.f;
    int d = q.s.f;
    int l = q.f.s;
    int r = q.s.s;
    if ( (r-l+1)*(d-u+1) == i ) {
      ++ans;
      ++i;
    } else {
      i = (r-l+1)*(d-u+1);
    }
  }
  return ans;
}

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