Submission #276622

#	Time	Username	Problem	Language	Result	Execution time	Memory
276622		Haunted_Cpp	Seats (IOI18_seats)	C++17	25 / 100	4070 ms	103544 KiB

seats

#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e9;
 
int H, W;
vector<int> R, C;
 
int LO = 0;
int HI = 0;

struct Node {
  int R_min, R_max;
  int C_min, C_max;
  Node() {
    R_min = C_min = INF;
    R_max = C_max = -INF;
  }
  void merge(Node l, Node r) {
    R_min = min(l.R_min, r.R_min);
    C_min = min(l.C_min, r.C_min);
    
    R_max = max(l.R_max, r.R_max);
    C_max = max(l.C_max, r.C_max);
  }
};
 
struct SegmentTree {
  vector<Node> seg;
  SegmentTree(const vector<int> &R, const vector<int> &C) {
    seg.resize(4 * R.size());
    //~ mx.resize(4 * arr.size());
    build(LO, HI - 1, 0, R, C);
  }
  void build(int l, int r, int node, const vector<int>&R, const vector<int>&C) {
    if (l == r) {
      seg[node].R_min = seg[node].R_max = R[l];
      seg[node].C_min = seg[node].C_max = C[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, (node << 1) + 1, R, C);
    build(mid + 1, r, (node << 1) + 2, R, C);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  void modify(int l, int r, int node, int delta, int where, bool which) {
    if (l == r) {
      if (which) {
        seg[node].R_max = seg[node].R_min = delta;
      } else {
        seg[node].C_max = seg[node].C_min = delta;
      }
      return;
    }
    int mid = (l + r) >> 1;
    if (where <= mid) {
      modify(l, mid, (node << 1) + 1, delta, where, which);
    }
    if (where >= mid + 1) {
      modify(mid + 1, r, (node << 1) + 2, delta, where, which);
    }
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  Node query(int ql, int qr, int l, int r, int node) {
    if (l >= ql && r <= qr) return seg[node];
    //~ if (l == r) return seg[node];
    int mid = (l + r) >> 1;
    Node esq;
    if (ql <= mid) {
      esq = query(ql, qr, l, mid, 2 * node + 1);
    }
    Node dir;
    if (qr >= mid + 1) {
      dir =  query(ql, qr, mid + 1, r, 2 * node + 2);
    }
    Node ans;
    ans.merge(esq, dir);
    return ans;
  }
};

SegmentTree *seg;
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  ::H = H; ::W = W;
  ::R = R; ::C = C;
  ::HI = H * W;
  seg = new SegmentTree(R, C);
}
 
int swap_seats(int a, int b) {
  swap(R[a], R[b]);
  swap(C[a], C[b]);
  //~ seg -> modify(LO, HI - 1, 0, R[a], a);
  //~ seg -> modify(LO, HI - 1, 0, R[b], b);
  seg -> modify(LO, HI - 1, 0, R[a], a, true); 
  seg -> modify(LO, HI - 1, 0, C[a], a, false); 
  seg -> modify(LO, HI - 1, 0, R[b], b, true);
  seg -> modify(LO, HI - 1, 0, C[b], b, false);
  int res = 0;
  int current_idx = 0;
  while(current_idx < HI) {
    Node ans = seg -> query(0, current_idx, LO, HI - 1, 0);
    //~ pair<int, int> A = rows_tree -> query(0, current_idx, LO, HI - 1, 0);
    //~ pair<int, int> B = cols_tree -> query(0, current_idx, LO, HI - 1, 0);
    int score = (ans.R_max - ans.R_min + 1) * (ans.C_max - ans.C_min + 1);
    if (current_idx + 1 == score) {
      ++res;
      ++current_idx;
    } else {
      current_idx = score - 1;
    }
  }
  return res;
}

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