Submission #1041592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041592		vjudge1	Tenis (COI19_tenis)	C++17	30 / 100	1064 ms	12004 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][3];

void modify(int p, int Ra[3], int idx, int s = 1, int e = n + 1, int v = 1)
{
  if(p < s || e <= p) return;
  if(e - s == 1)
    {
      for(int i = 0; i < 3; i++)
	seg[v][idx][i] = Ra[i];
      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);
  
  for(int i = 0; i < 3; i++)
    seg[v][idx][i] = min(seg[lc][idx][i], seg[rc][idx][i]);
}

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

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

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

int query(int X)
{
  int BR[3] = {};
  for(int i = 0; i < 3; i++)
    BR[i] = R[X][i];

  while(true)
    {
      int prv[] = {BR[0], BR[1], BR[2]};

      for(int i = 0; i < 3; i ++)
	{
	  int bc[3] = {INF, INF, INF};
	  get(prv[i], 0, bc);
	  for(int j = 0; j < 3; j++)
	    BR[j] = min(BR[j], bc[j]);
	}
      
      bool same = true;
      for(int i = 0; i < 3; i ++)
	same &= (prv[i] == BR[i]);
      
      if(same) break;
    }
  
  return min(BR[0], min(BR[1], BR[2]));
}

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: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 49