Submission #772817

#	Time	Username	Problem	Language	Result	Execution time	Memory
772817		I_Love_EliskaM_	Seats (IOI18_seats)	C++14	31 / 100	4101 ms	60668 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);

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 swap_seats(int x, int y) {
  swap(r[x],r[y]);
  swap(c[x],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;
  }

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

  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: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30