Submission #594634

#	Time	Username	Problem	Language	Result	Execution time	Memory
594634		Sam_a17	자리 배치 (IOI18_seats)	C++14	11 / 100	4075 ms	77244 KiB

seats

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

#define pb push_back
#define ld long double
#define ll long long

#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define lb lower_bound
#define ub upper_bound

const int N = 1e6 + 10, inf = 1e9;
struct segTree {
  struct node {
    int value, maxX, minX, maxY, minY, lazy;
  };
  vector<node> tree;
  int size;

  void init(int n) {
    size = 1;
    while(size < n)  {
      size *= 2;
    }
    tree.assign(2 * size - 1, {0, -inf, inf, -inf, inf, -1});
  }

  node combine(node a, node b) {
    a.maxX = max(a.maxX, b.maxX);
    a.maxY = max(a.maxY, b.maxY);

    a.minX = min(a.minX, b.minX);
    a.minY = min(a.minY, b.minY);

    a.value += b.value;
    a.lazy = -1;
    return a;
  }

   void shift(int x, int lx, int rx) {
    if(rx - lx == 1 || tree[x].lazy == -1) {
      tree[x].lazy = -1;
      return;
    }
 
    int mid = (lx + rx) / 2;
    tree[2 * x + 1].lazy = tree[x].lazy;
    tree[2 * x + 1].value = tree[x].lazy * (mid - lx);
 
    tree[2 * x + 2].lazy = tree[x].lazy;
    tree[2 * x + 2].value = tree[x].lazy * (rx - mid);
 
    tree[x].lazy = -1;  
  }
 
  void upd_interval(int l, int r, int v, int x, int lx, int rx) {
    shift(x, lx, rx);
  
    if(lx >= r || rx <= l) {
      return;
    }
    
    if(lx >= l && rx <= r) {
      tree[x].value = v;
      tree[x].lazy = v;
      shift(x, lx, rx);
      return;
    }
 
    int mid = (lx + rx) / 2;
    upd_interval(l, r, v, 2 * x + 1, lx, mid);
    upd_interval(l, r, v, 2 * x + 2, mid, rx);
 
    tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void upd_interval(int l, int r, int v) {
    upd_interval(l, r, v, 0, 0, size);
  }
 
  void upd(int u, int X, int Y, int v, int x, int lx, int rx) {
    shift(x, lx, rx);
    if(rx - lx == 1) {
      if(X != -1) {
        tree[x].maxX = tree[x].minX = X;
        tree[x].maxY = tree[x].minY = Y;
      }

      if(v != -1) {
        tree[x].value = v;
      }
      return;
    }
 
    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, X, Y, v, 2 * x + 1, lx, m);
    }else {
      upd(u, X, Y, v, 2 * x + 2, m, rx);
    }
    tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  }
 
  void upd(int u, int X, int Y, int v) {
    upd(u, X, Y, v, 0, 0, size);
  }
 
  node qry (int l, int r, int x, int lx, int rx) {
    shift(x, lx, rx);
    if(l >= rx || lx >= r) {
      return {0, -inf, inf, -inf, inf, -1};
    }
    if(lx >= l && r >= rx) {
      return tree[x];
    }
 
    int m = (rx + lx) / 2;
    node s1 = qry(l, r, 2 * x + 1, lx, m);
    node s2 = qry(l, r, 2 * x + 2, m, rx);
    return combine(s1, s2);
  }
 
  node qry(int l, int r) {
    return qry(l, r, 0, 0, size);
  }
};

int n, h, w, r[N], c[N], ans[N], answ;
segTree x;

int getSum(int x1, int y1, int x2, int y2) {
  return x2 * y2 - (x1 - 1) * y2 - x2 * (y1 - 1) + (x1 - 1) * (y1 - 1);
}

int swap_seats(int a, int b) {
  bool flag = false;
  if(max(h, w) < 1000) {
    flag = true;
  }
    if(a > b) {
      swap(a, b);
    } a++, b++;

    swap(r[a], r[b]);
    swap(c[a], c[b]);

    x.upd(a, r[a], c[a], -1);
    x.upd(b, r[b], c[b], -1);

    auto an = x.qry(0, a);

    int minX, maxX, minY, maxY;
    
    minX = an.minX, maxX = an.maxX; 
    minY = an.minY, maxY = an.maxY;

    if(!flag) {
      for(int i = a; i <= b; i++) {
        minX = min(minX, r[i]);
        maxX = max(maxX, r[i]);
        //
        minY = min(minY, c[i]);
        maxY = max(maxY, c[i]);

        int sum = getSum(minX, minY, maxX, maxY);
        if(sum == i && !ans[i]) {
          ans[i] = 1;
          x.upd(i, -1, -1, 1);
          answ++;
        } else if(sum != i) {
          if(ans[i] == 1) {
            ans[i] = 0;
            x.upd(i, -1, -1, 0);
            answ--;
          }
        }
      }
    } else {
      answ -= x.qry(a, b + 1).value;
      x.upd_interval(a, b + 1, 0);

      for(int i = a; i <= b; i++) {

        auto an = x.qry(0, i + 1);
        int minX, maxX, minY, maxY;
        
        minX = an.minX, maxX = an.maxX; 
        minY = an.minY, maxY = an.maxY;

        int sum = getSum(minX, minY, maxX, maxY);
        if(sum == i) {
          x.upd(i, -1, -1, 1);
          answ++;
        } else if(sum > i) {
          i = sum - 1;
        }
      }
    }

    return answ;

}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  n = sz(R), h = H, w = W;
  x.init(n + 2);

  int minX, maxX, minY, maxY;
  for(int i = 0; i < n; i++) {
    r[i + 1] = R[i];
    c[i + 1] = C[i];

    x.upd(i + 1, R[i], C[i], -1);

    if(i == 0) {
      answ++, ans[i + 1] = 1;
      x.upd(i + 1, -1, -1, 1);

      minX = maxX = R[i];
      minY = maxY = C[i];
    } else {
      //
      minX = min(minX, R[i]);
      maxX = max(maxX, R[i]);

      //
      minY = min(minY, C[i]);
      maxY = max(maxY, C[i]);

      if(getSum(minX, minY, maxX, maxY) == (i + 1)) {
        x.upd(i + 1, -1, -1, 1);
        ans[i + 1] = 1;
        answ++;
      }
    }
  }
}

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