제출 #871487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871487		NeroZein	Tenis (COI19_tenis)	C++17	100 / 100	279 ms	7964 KiB

tenis

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 1e5 + 5;

int lazy[N * 2], seg[N * 2];

void push(int nd, int l, int r) {
  if (!lazy[nd]) return;
  seg[nd] += lazy[nd];
  if (l != r) {
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    lazy[nd + 1] += lazy[nd];
    lazy[rs] += lazy[nd];
  }
  lazy[nd] = 0;
}

void upd(int nd, int l, int r, int s, int e, int v) {
  push(nd, l, r);
  if (l >= s && r <= e) {
    lazy[nd] = v;
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    upd(nd + 1, l, mid, s, e, v); 
    push(rs, mid + 1, r); 
  } else {
    if (mid < s) {
      push(nd + 1, l, mid);
      upd(rs, mid + 1, r, s, e, v); 
    } else {
      upd(nd + 1, l, mid, s, e, v); 
      upd(rs, mid + 1, r, s, e, v);       
    }
  }
  seg[nd] = min(seg[nd + 1], seg[rs]); 
}

int get(int nd, int l, int r) {
  if (l == r) {
    return l;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  push(nd + 1, l, mid);
  push(rs, mid + 1, r);
  if (seg[nd + 1] == -1) {
    return get(nd + 1, l, mid);
  }
  return get(rs, mid + 1, r); 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, q;
  cin >> n >> q;
  vector<vector<int>> a(3, vector<int> (n)); 
  vector<vector<int>> idx(3, vector<int> (n)); 
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
      --a[i][j]; 
      idx[i][a[i][j]] = j; 
    }
  }
  auto get_first = [&](int x) {
    return min({idx[0][x], idx[1][x], idx[2][x]}); 
  };
  auto get_last = [&](int x) {
    return max({idx[0][x], idx[1][x], idx[2][x]}); 
  };
  auto fill = [&](int x, int y) {
    vector<int> ret;
    for (int i = 0; i < 3; ++i) {
      ret.push_back(idx[i][x]); 
      ret.push_back(idx[i][y]); 
    }
    sort(ret.begin(), ret.end());
    ret.resize(unique(ret.begin(), ret.end()) - ret.begin()); 
    return ret;
  };
  auto get_val = [&](int col) {
    return max({get_last(a[0][col]), get_last(a[1][col]), get_last(a[2][col])}); 
  };
  vector<int> b(n); 
  for (int i = 0; i < n; ++i) {
    b[i] = get_val(i); 
    upd(0, 0, n - 1, i, i, b[i]); 
    upd(0, 0, n - 1, get_last(i), n - 1, -1); 
  }
  while (q--) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      int x;
      cin >> x;
      --x;
      int f = get_first(x);
      int c = get(0, 0, n - 1);
      cout << (c >= f ? "DA" : "NE") << '\n'; 
    } else {
      int p, x, y;
      cin >> p >> x >> y;
      --p, --x, --y;
      upd(0, 0, n - 1, get_last(x), n - 1, +1);
      upd(0, 0, n - 1, get_last(y), n - 1, +1);
      vector<int> cols = fill(x, y); 
      for (int i : cols) {
        upd(0, 0, n - 1, i, i, -b[i]); 
      }
      int px = idx[p][x];
      int py = idx[p][y];
      swap(idx[p][x], idx[p][y]); 
      a[p][px] = y;
      a[p][py] = x; 
      upd(0, 0, n - 1, get_last(x), n - 1, -1);
      upd(0, 0, n - 1, get_last(y), n - 1, -1);
      for (int i : cols) {
        b[i] = get_val(i); 
        upd(0, 0, n - 1, i, i, b[i]); 
      }
    }
  }
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 49 / 49