Submission #772625

#	Time	Username	Problem	Language	Result	Execution time	Memory
772625		I_Love_EliskaM_	Seats (IOI18_seats)	C++14	0 / 100	4062 ms	67532 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<int> mn,mx; int sz=1;
  sgt(int n) {
    while (sz<n) sz<<=1;
    mn.assign(2*sz-1,inf);
    mx.assign(2*sz-1,0);
  }
  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]=min(mn[2*v+1],mn[2*v+2]);
    mx[v]=max(mx[2*v+1],mx[2*v+2]);
  }
  void set(int i, int x) {
    mn[sz-1+i]=mx[sz-1+i]=x;
    upd(0,0,sz,i);
  }

  pi query(int v, int l, int r, int lx, int rx) {
    if (rx<=l || r<=lx) return {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,rq.f) , max(lq.s,rq.s) };
  }
  pi query(int l, int r) {
    return query(0,0,sz,l,r);
  }
  int qmin(int l, int r) {
    auto q = query(0,0,sz,l,r);
    return q.f;
  }
  int qmax(int l, int r) {
    auto q = query(0,0,sz,l,r);
    return q.s;
  }
};
sgt stx(1e6), sty(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) stx.set(i,r[i]), sty.set(i,c[i]); 
}

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

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

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