Submission #594619

#	Time	Username	Problem	Language	Result	Execution time	Memory
594619		Sam_a17	Seats (IOI18_seats)	C++14	0 / 100	4061 ms	56764 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 maxX, minX, maxY, minY;
  };
  vector<node> tree;
  int size;

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

  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);
    return a;
  }

  void upd(int u, int X, int Y, int x, int lx, int rx) {
    if(rx - lx == 1) {
      tree[x] = {X, X, Y, Y};
      return;
    }

    int m = (lx + rx) / 2;
    if(u < m) {
      upd(u, X, Y, 2 * x + 1, lx, m);
    }else {
      upd(u, X, Y, 2 * x + 2, m, rx);
    }
    tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
  }

  void upd(int u, int X, int Y) {
    upd(u, X, Y, 0, 0, size);
  }

  node qry (int l, int r, int x, int lx, int rx) {
    if(l >= rx || lx >= r) {
      return {-inf, inf, -inf, inf};
    }
    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) {
  if(abs(a - b) && max(h ,w) > 1000) {
    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]);
    x.upd(b, r[b], c[b]);

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

    int minX, maxX, minY, maxY;
    
    minX = an.minX, maxX = an.maxX; 
    minY = an.minY, maxY = an.maxY;
  
    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;
        answ++;
      } else if(sum != i) {
        if(ans[i] == 1) {
          ans[i] = 0;
          answ--;
        }
      }
    }

    return answ;
  } else {
    
    int i = 1; answ = 0;
    while(i <= n) {
      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) {
        answ++;
      } else {
        i = sum - 1;
      }
    }
  }
}

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]);

    if(i == 0) {
      answ++, ans[i + 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)) {
        ans[i + 1] = 1;
        answ++;
      }
    }
  }
}

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:144:1: warning: control reaches end of non-void function [-Wreturn-type]
  144 | }
      | ^

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