Submission #225996

#	Time	Username	Problem	Language	Result	Execution time	Memory
225996		quocnguyen1012	Tenis (COI19_tenis)	C++14	100 / 100	245 ms	7928 KiB

tenis

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5, inf = 1e9;

int tr[4 * maxn], lz[4 * maxn];
int N, Q;
int pos[3][maxn], a[3][maxn];

#define lc id << 1
#define rc id << 1 | 1

void push(int id, int l, int r)
{
  if(l != r){
    tr[lc] += lz[id];
    tr[rc] += lz[id];
    lz[lc] += lz[id];
    lz[rc] += lz[id];
  }
  lz[id] = 0;
}

void modify(int id, int l, int r, int L, int R, int v)
{
  push(id, l, r);
  if(r < L || R < l)
    return;
  if(L <= l && r <= R){
    tr[id] += v;
    lz[id] += v;
    push(id, l, r);
    return;
  }
  int mid = (l + r) / 2;
  modify(lc, l, mid, L, R, v); modify(rc, mid + 1, r, L, R, v);
  tr[id] = min(tr[lc], tr[rc]);
}

int get(int id, int l, int r, int L, int R)
{
  push(id, l, r);
  if(r < L || R < l)
    return inf;
  if(L <= l && r <= R){
    return tr[id];
  }
  int mid = (l + r) / 2;
  return min(get(lc, l, mid, L, R), get(rc, mid + 1, r, L, R));
}

int query(int id, int l, int r)
{
  push(id, l, r);
  if(l == r)
    return l;
  int mid = (l + r) / 2;
  if(tr[lc] == 0)
    return query(lc, l, mid);
  return query(rc, mid + 1, r);
}

int maxi(int p)
{
  int mx = 0;
  for(int i = 0; i < 3; ++i)
    mx = max(mx, pos[i][p]);
  return mx;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> Q;
  for(int i = 0; i < 3; ++i){
    for(int j = 1; j <= N; ++j){
      cin >> a[i][j];
      pos[i][a[i][j]] = j;
    }
  }
  for(int i = 1; i <= N; ++i){
    modify(1, 1, N, i, i, i);
  }
  for(int i = 1; i <= N; ++i){
    modify(1, 1, N, maxi(i), N, -1);
  }
  for(int tc = 1; tc <= Q; ++tc){
    int type; cin >> type;
    if(type == 1){
      int p; cin >> p;
      cout << (maxi(p) <= query(1, 1, N) ? "DA" : "NE");
      cout << '\n';
    }
    else{
      int t, x, y; cin >> t >> x >> y; --t;
      modify(1, 1, N, maxi(x), N, 1);
      modify(1, 1, N, maxi(y), N, 1);
      swap(pos[t][x], pos[t][y]);
      modify(1, 1, N, maxi(x), N, -1);
      modify(1, 1, N, maxi(y), N, -1);
    }
  }
}

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