oj.uz

Submission #1041505

# Submission time Handle Problem Language Result Execution time Memory
1041505 2024-08-02T04:53:36 Z vjudge1 Tenis (COI19_tenis) C++17
0 / 100
 500 ms 8152 KB 
#include<bits/stdc++.h>

using namespace std;

#define INF INT_MAX
const int N = 100'000 + 100, M = (2 << 17) + 10;
int n, q, p[3][N];
int R[N][3], seg[M][3];

void modify(int p, int Ra, int idx, int s = 1, int e = n + 1, int v = 1)
{
  if(p < s || e <= p) return;
  if(e - s == 1)
    {
      seg[v][idx] = Ra;
      return;
    }
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  modify(p, Ra, idx, s, mid, lc);
  modify(p, Ra, idx, mid, e, rc);
  seg[v][idx] = min(seg[lc][idx], seg[rc][idx]);
}

int get(int l, int idx, int r = n + 1, int s = 1, int e = n + 1, int v = 1)
{
  if(r <= s || e <= l) return INF;
  if(l <= s && e <= r) return seg[v][idx];
  int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
  return min(get(l, idx, r, s, mid, lc), get(l, idx, r, mid, e, rc));
}

int BEST(int X) {
  return min(R[X][0], min(R[X][1], R[X][2]));
}

void update(int X)
{
  int bestrank = BEST(X);
  for(int i = 0; i < 3; i ++)
    modify(R[X][i], bestrank, i);
}

int query(int X)
{
  int ans = BEST(X);
  for(int i = 0; i < 3; i++)
    for(int j = 0; j < 3; j++)
      for(int k = 0; k < 3; k++)
	{
	  int D = get(R[X][i], i);
	  int Ply = p[j][D];
	  if(R[Ply][i] < R[X][i]) continue;
	  
	  int D2 = get(R[Ply][j], j);
	  int Ply2 = p[k][D2];
	  
	  if(R[Ply2][j] < R[Ply][j]) continue;

	  int D3 = get(R[Ply2][k], k);
	  ans = min(ans, D3);
	}
  return ans;
}

int main()
{
  cin >> n >> q;

  for(int j = 0; j < 3; j++)
    for(int i = 1; i <= n; i ++) {
      cin >> p[j][i];
      R[p[j][i]][j] = i;
    }

  for(int i = 1; i <= n; i ++)
    update(i);

  while(q--)
    {
      int t;
      cin >> t;
      if(t == 1)
	{
	  int X;
	  cin >> X;
	  int bestposs = query(X);
	  cout << (bestposs == 1 ? "DA" : "NE") << '\n';
	}
      else
	{
	  int P, A, B;
	  cin >> P >> A >> B;
	  P--;
	  int ra = R[A][P], rb = R[B][P]; 
	  swap(p[P][ra], p[P][rb]);
	  swap(R[A][P], R[B][P]);
	  update(A);
	  update(B);
	}
    }
  
  
  return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 588 ms 8152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 49.0

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