oj.uz

Submission #225992

# Submission time Handle Problem Language Result Execution time Memory
225992 2020-04-22T09:19:54 Z quocnguyen1012 Tenis (COI19_tenis) C++14
0 / 100
 133 ms 7608 KB 
#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)
{
  tr[id] += lz[id];
  if(l != r){
    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){
    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);
  }
  while(Q--){
    int type; cin >> type;
    ///for(int i = 1; i <= N; ++i)
      ///cerr << get(1, 1, N, i, i) << " \n"[i == N];
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 7608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -