Submission #1192968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192968		Lemser	Seats (IOI18_seats)	C++20	0 / 100	169 ms	109884 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;

using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;

#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()

#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)

bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

void valid(ll in) { cout<<((in)?"YES\n":"NO\n"); }
ll lcm(ll a, ll b) { return (a/gcd(a,b))*b; }
ll gauss(ll n) { return (n*(n+1))/2; }

const ll INF = 1e18;

struct SegTree {
  struct Node {
    ll mn, cnt;
    
    Node ( ) {  }
    Node (ll mn, ll cnt): mn(mn), cnt(cnt) {  }

    Node operator +(const Node &o) {
      return {
        min(mn, o.mn),
        (mn <= o.mn ? cnt : 0) +
        (o.mn <= mn ? o.cnt : 0)
      };
    };
  };

  Node IDEM = {0, 1};
  vector<Node> st;
  vll lz;
  ll n;

  SegTree () {  }
  SegTree (ll n): st(4*n+4, IDEM), lz(4*n+4,0), n(n) {  }

  void push (ll id, ll l, ll r) {
    st[id].mn += lz[id];
    if (l != r) {
      lz[id*2] += lz[id];
      lz[id*2+1] += lz[id];
    }
    lz[id] = 0;
  }

  void update (ll l, ll r, ll c) { update(1, 0, n-1, l, r, c); }
  void update (ll id, ll l, ll r, ll i, ll j, ll c) {
    push(id, l, r);
    if (r < i || j < l) return;
    if (i <= l && r <= j) {
      lz[id] += c;
      push(id, l, r);
      return;
    }
    ll m = (l+r)/2;
    update(id*2, l, m, i, j, c);
    update(id*2+1, m+1, r, i, j, c);
    st[id] = st[id*2] + st[id*2+1];
  }
  
};

const int N = 1e6 + 7;
vector<vll> a;
pll pos[N];
ll h, w;
SegTree st;

ll num (ll i, ll j) { return (0 <= i && i < h && 0 <= j && j < w ? a[i][j] : h*w); }
void upd (ll i, ll j, ll c) {
  vll vec;
  vec.pb(num(i-1, j-1));
  vec.pb(num(i-1, j));
  vec.pb(num(i, j-1));
  vec.pb(num(i, j));
  sort(all(vec));
  st.update(vec[0], vec[1]-1, +c);
  if (vec[2] < h*w) st.update(vec[2], vec[3]-1, +c);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  h = H;
  w = W;
  st = SegTree(h*w);
  fo (i, W) a[R[i]][C[i]] = i;
  fo (i, W) pos[i] = {R[i], C[i]};
  fo (i, H+1) {
    fo (j, W+1) {
      upd(i, j, +1);
    }
  }
}

int swap_seats(int x, int y) {
  ll ix = pos[x].fi, jx = pos[x].se;
  ll iy = pos[y].fi, jy = pos[y].se;
  set<pll> ds;
  ds.insert({ix, jx});
  ds.insert({ix+1, jx});
  ds.insert({ix, jx+1});
  ds.insert({ix+1, jx+1});
  ds.insert({iy, jy});
  ds.insert({iy+1, jy});
  ds.insert({iy, jy+1});
  ds.insert({iy+1, jy+1});
  for (auto [i, j]: ds) upd(i, j, -1);
  swap(a[ix][jx], a[iy][jy]);
  swap(pos[x], pos[y]);
  for (auto [i, j]: ds) upd(i, j, +1);
  auto ans = st.st[1];
  return (ans.mn == 4 ? ans.cnt : 0);
}

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