Submission #1193551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193551		KG07	Hieroglyphs (IOI24_hieroglyphs)	C++20	0 / 100	1132 ms	1611892 KiB

hieroglyphs

#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> I = {-1};
struct segment_tree{
  int n;
  int M[300000];
  void init(int N, int l, int r){
    if(l == r)M[N] = n;
    else{
      init(2*N, l, (l+r)/2);
      init(2*N+1, (l+r)/2+1, r);
    }
  }
  void update(int N, int x, int y, int l, int r){
    if(x < l || x > r)return;
    if(l == x && x == r){
      M[N] = min(M[N], y);
      return;
    }
    update(2*N, x, y, l, (l+r)/2);
    update(2*N+1, x, y, (l+r)/2+1, r);
    M[N] = min(M[2*N], M[2*N+1]);
  }
  int get_left(int N, int z, int l, int r){
    if(z < l)return n;
    if(z >= r)return M[N];
    return min(get_left(2*N, z, l, (l+r)/2), get_left(2*N+1, z, (l+r)/2+1, r));
  }
  int get_right(int N, int z, int l, int r){
    if(z > r)return n;
    if(z <= l)return M[N];
    return min(get_right(2*N, z, l, (l+r)/2), get_right(2*N+1, z, (l+r)/2+1, r));
  }
} T;
struct indexes{
  vector<int> A[200002], B[200002], C, D, E;
  int F[200002];
  vector<pair<pair<int, int>, pair<int, int>>> e, f;
  bool is_sq(int a, int b, int c, int d){
    return A[a][c-1] < A[b][A[b].size()-d] && B[a][c-1] < B[b][B[b].size()-d];
  }
  bool init(vector<int> a, vector<int> b){
    for(int i = 0; i < a.size(); i++)A[a[i]].push_back(i);
    for(int i = 0; i < b.size(); i++)B[b[i]].push_back(i);
    C.clear(), D.clear(), E.clear();
    for(int i:a)if(A[i].size() <= B[i].size())C.push_back(i);
    for(int i:b)if(A[i].size() >= B[i].size())D.push_back(i);
    int N = C.size();
    int M = D.size();
    int x = 0, y = 0;
    while(x < N || y < M){
      if(x || y)F[E[E.size()-1]]++;
      e.push_back(make_pair(make_pair(0, 0), make_pair(0, 0)));
      f.push_back(make_pair(make_pair(0, 0), make_pair(0, 0)));
      if(x == N){
        E.push_back(D[y++]);
        continue;
      }
      if(y == M){
        E.push_back(C[x++]);
        continue;
      }
      if(A[C[x]].size() == B[C[x]].size() || A[D[y]].size() == B[D[y]].size()){
        if(C[x] == D[y]){
          E.push_back(D[y++]);
          x++;
          continue;
        }
        if(A[C[x]].size() != B[C[x]].size()){
          E.push_back(C[x++]);
          continue;
        }
        if(A[D[y]].size() != B[D[y]].size()){
          E.push_back(D[y++]);
          continue;
        }
        return true;
      }
      bool X = is_sq(C[x], D[y], F[C[x]]+1, B[D[y]].size()-F[D[y]]), Y = is_sq(D[y], C[x], F[D[y]]+1, A[C[x]].size()-F[C[x]]);
      if(X && Y)return true;
      if(Y){
        E.push_back(D[y++]);
        continue;
      }
      if(X){
        E.push_back(C[x++]);
        continue;
      }
      return true;
    }
    return false;
  }
  bool check_sq(vector<int> a, vector<int> b){
    for(int i:E)F[i] = 0;
    T.init(1, 1, T.n);
    for(int i = 0; i < E.size(); i++){
      if(!F[E[i]])e[i].first.first = A[E[i]][0];
      else{
        int t = T.get_right(1, F[E[i]], 1, T.n);
        int l = 0, r = A[E[i]].size()-1;
        while(l < r){
          int c = (l+r)/2;
          if(A[E[i]][c] > t)r = c;
          else l = c+1;
        }
        e[i].first.first = A[E[i]][l];
      }
      F[E[i]] = i+1;
      T.update(1, i+1, e[i].first.first, 1, T.n);
    }
    for(int i:E)F[i] = T.n;
    T.init(1, 1, T.n);
    for(int i = E.size()-1; i >= 0; i--){
      if(F[E[i]] == T.n)e[i].first.second = A[E[i]][A[E[i]].size()-1];
      else{
        int t = T.n-T.get_left(1, F[E[i]]+1, 1, T.n);
        int l = 0, r = A[E[i]].size()-1;
        while(l < r){
          int c = (l+r+1)/2;
          if(A[E[i]][c] < t)l = c;
          else r = c-1;
        }
        e[i].first.second = A[E[i]][r];
      }
      F[E[i]] = i;
      T.update(1, i+1, T.n-e[i].first.second, 1, T.n);
    }
    for(int i:E)F[i] = 0;
    T.init(1, 1, T.n);
    for(int i = 0; i < E.size(); i++){
      if(!F[E[i]])e[i].second.first = B[E[i]][0];
      else{
        int t = T.get_right(1, F[E[i]], 1, T.n);
        int l = 0, r = B[E[i]].size()-1;
        while(l < r){
          int c = (l+r)/2;
          if(B[E[i]][c] > t)r = c;
          else l = c+1;
        }
        e[i].second.first = B[E[i]][l];
      }
      F[E[i]] = i+1;
      T.update(1, i+1, e[i].second.first, 1, T.n);
    }
    for(int i:E)F[i] = T.n;
    T.init(1, 1, T.n);
    for(int i = E.size()-1; i >= 0; i--){
      if(F[E[i]] == T.n)e[i].second.second = B[E[i]][B[E[i]].size()-1];
      else{
        int t = T.n-T.get_left(1, F[E[i]]+1, 1, T.n);
        int l = 0, r = B[E[i]].size()-1;
        while(l < r){
          int c = (l+r+1)/2;
          if(B[E[i]][c] < t)l = c;
          else r = c-1;
        }
        e[i].second.second = B[E[i]][r];
      }
      F[E[i]] = i;
      T.update(1, i+1, T.n-e[i].second.second, 1, T.n);
    }
    int c, d;
    c = 0, d = 0;
    for(int i = 0; i < E.size(); i++){
      while(a[c] != E[i])c++;
      f[i].first.first = c++;
      while(b[d] != E[i])d++;
      f[i].second.first = d++;
    }
    c = a.size()-1, d = b.size()-1;
    for(int i = E.size()-1; i >= 0; i--){
      while(a[c] != E[i])c--;
      f[i].first.second = c--;
      while(b[d] != E[i])d--;
      f[i].second.second = d--;
    }
    T.n = a.size();
    T.init(1, 1, T.n);
    for(int i = 0; i < E.size(); i++){
      if(A[E[i]].size() <= B[E[i]].size())T.update(1, f[i].first.first, e[i].second.first, 1, T.n);
      if(B[E[i]].size() <= A[E[i]].size() && f[i].second.second <= T.get_right(1, e[i].first.second, 1, T.n))return true;
    }
    T.n = b.size();
    T.init(1, 1, T.n);
    for(int i = 0; i < E.size(); i++){
      if(B[E[i]].size() <= A[E[i]].size())T.update(1, f[i].second.first, e[i].first.first, 1, T.n);
      if(A[E[i]].size() <= B[E[i]].size() && f[i].first.second <= T.get_right(1, e[i].second.second, 1, T.n))return true;
    }
    return false;
  }
} H;

vector<int> ucs(vector<int> A, vector<int> B) {
  int N = A.size(), M = B.size();
  if(H.init(A, B))return I;
  T.n = H.E.size();
  if(H.check_sq(A, B))return I;
  return H.E;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42