Submission #1242349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242349		SalihSahin	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	137 ms	36012 KiB

hieroglyphs

#include "hieroglyphs.h"
#include "bits/stdc++.h"
using namespace std;
#define pb push_back

const int MAXA = 2e5 + 5;

struct SEGT{
  vector<array<int, 3> > tree;

  void init(int n){
    tree.assign(4*n, {0, 0, 0});
  }

  void update(int ind, int l, int r, int pos, array<int, 3> val){
    if(l == r){
      tree[ind] = max(tree[ind], val);
    }
    else{
      int m = (l + r)/2;

      if(pos <= m) update(ind*2, l, m, pos, val);
      else update(ind*2+1, m+1, r, pos, val);

      tree[ind] = max(tree[ind*2], tree[ind*2+1]);
    }
  }

  array<int, 3> query(int ind, int l, int r, int ql, int qr){
    if(l > r || ql > qr || l > qr || r < ql) return {0, 0, 0};
    if(l >= ql && r <= qr){
      return tree[ind];
    }
    else{
      int m = (l + r)/2;

      return max(query(ind*2, l, m, ql, qr), query(ind*2+1, m+1, r, ql, qr));
    }
  }
};

struct SEGT2{
  vector<int> tree;

  void init(int n){
    tree.assign(4*n, 0);
  }

  void update(int ind, int l, int r, int pos, int val){
    if(l == r){
      tree[ind] += val;
    }
    else{
      int m = (l + r)/2;

      if(pos <= m) update(ind*2, l, m, pos, val);
      else update(ind*2+1, m+1, r, pos, val);

      tree[ind] = (tree[ind*2] + tree[ind*2+1]);
    }
  }

  int query(int ind, int l, int r, int ql, int qr){
    if(l > r || ql > qr || l > qr || r < ql) return 0;
    if(l >= ql && r <= qr){
      return tree[ind];
    }
    else{
      int m = (l + r)/2;

      return (query(ind*2, l, m, ql, qr) + query(ind*2+1, m+1, r, ql, qr));
    }
  }
};

vector<pair<int, int> > ind2[MAXA];

vector<int> ucs(vector<int> A, vector<int> B){
  int n = A.size(), m = B.size();

  vector<int> ind[MAXA];
  for(int i = 0; i < m; i++){
    ind[B[i]].pb(i+1);
  }

  vector<int> cnt(MAXA);
  for(int i = 0; i < n; i++){
    cnt[A[i]] = 1;
  }
  for(int i = 0; i < m; i++){
    if(cnt[B[i]] == 1){
      cnt[B[i]] = 2;
    }
  }

  for(int i = 0; i < MAXA; i++){
    if(ind[i].size() == 1){
      ind[i].pb(ind[i][0]);
    }
  }

  vector<vector<int> > dp(n, vector<int>(2));
  vector<vector<pair<int, int> > > par(n, vector<pair<int, int> >(2));
  SEGT seg;
  seg.init(m);
  array<int, 3> maxlis = {0, 0, 0};

  for(int i = 0; i < n; i++){
    if(ind[A[i]].size() == 0) continue; // b de bu eleman yok

    for(int j = 0; j < 2; j++){
      int pos2 = ind[A[i]][j];
      array<int, 3> arr = seg.query(1, 1, m, 1, pos2 - 1);
      if(arr[0] + 1 > dp[i][j]){
        dp[i][j] = max(dp[i][j], arr[0] + 1);
        par[i][j] = {arr[1], arr[2]};
      }
      maxlis = max(maxlis, {dp[i][j], i, j});
    }
    for(int j = 0; j < 2; j++){
      int pos2 = ind[A[i]][j];
      seg.update(1, 1, m, pos2, {dp[i][j], i, j});
    }
  }

  // condition 1: 2 farklı max size candidate olamaz (1 tane varsa onu checkleyecegiz) ve bu butun subseqleri kapsamalı
  // birden fazla degerden lis alabilen i, j degerleri bad; sondan geriye tracklerken bad node yoksa devam
  // condition 2: max size candidate degerim butun ortak elemanları kapsamalı => 1 ve 2 size olanlar için sağlaması yeterli (k <= 3)
  bool checklen1 = 1;
  int same = 0;
  for(int i = 0; i < MAXA; i++){
    if(cnt[i] == 2){
      same++;
    }
  }
  if(same != maxlis[0]){
    checklen1 = 0;
  }

  vector<int> ans;
  pair<int, int> p = {maxlis[1], maxlis[2]};
  while(p != make_pair(0, 0)){
    ans.pb(A[p.first]);
    p = par[p.first][p.second];
  }
  reverse(ans.begin(), ans.end());
  /*
  for(auto itr: ans){
    cout<<itr<<" ";
  }
  cout<<endl;
  */

  bool checklen2 = 1; // x...y...x,  y...x...y gelirse 2 farklı order oldugundan -1 yoksa ans yazdırcaz
  // A'da 2, B'de 1 tane olanlar için rangeye gelince pozisyonunu updatele, A'da 1 B'de 2 olanlar için query at 0 değilse checklen2 = 0


  
  for(int i = 0; i < n; i++){
    ind2[A[i]].pb({0, i});
  }
  for(int i = 0; i < m; i++){
    ind2[B[i]].pb({1, i});
  }
  
  
  vector<array<int, 3> > upd;
  for(int i = 0; i < MAXA; i++){
    if(ind2[i].size() == 3){
      int type = 0;
      vector<int> fa, fb;
      for(auto itr: ind2[i]){
        type += itr.first;
        if(itr.first == 0) fa.pb(itr.second);
        else fb.pb(itr.second);
      }

      if(type == 1){ // 2 tane A, 1 tane B
         upd.pb({fa[0], fb[0], 1});
         upd.pb({fa[1]+1, fb[0], -1});
      }
    }
  }
  
  SEGT2 seg2;
  seg2.init(m);
  
  sort(upd.begin(), upd.end());
  int indupd = 0;
  for(int i = 0; i < n; i++){
    while(indupd < upd.size() && upd[indupd][0] <= i){
      seg2.update(1, 1, m, upd[indupd][1], upd[indupd][2]);
      indupd++;
    }

    if(ind2[A[i]].size() == 3){
      int type = 0;
      vector<int> fa, fb;
      for(auto itr: ind2[A[i]]){
        type += itr.first;
        if(itr.first == 0) fa.pb(itr.second);
        else fb.pb(itr.second);
      }

      if(type == 2){
         int val = seg2.query(1, 1, m, fb[0], fb[1]);
         if(val > 0) checklen2 = 0;
      }
    }
  }
  

  if(!checklen1 || !checklen2) return {-1};
  else return ans;
}

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