Submission #1041556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041556		vjudge1	Tenis (COI19_tenis)	C++17	7 / 100	1073 ms	6100 KiB

tenis

#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++)
	for(int l = 0; l < 3; l++)
	  {
	    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);
	    int Ply3 = p[l][D3];

	    if(R[Ply3][k] < R[Ply2][k]) continue;

	    int D4 = get(R[Ply3][l], l);
	    ans = min(ans, D4);
	}
  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: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49