#include "hieroglyphs.h" #include <bits/stdc++.h> using namespace std; using ll = int; using pii = pair<ll,ll>; using vi = vector<ll>; const ll Nm = 2e5+5; map<ll,ll> xopn,yopn; //open on x/y: # -> count set<ll> sovlp; //set of overlap set<ll> xblk,yblk; //x/y blocked: cannot do GREATER than this term void insx(ll x0) { if (xopn.find(x0)==xopn.end()) { xopn[x0]=0; } xopn[x0]++; if (xopn.find(x0)!=xopn.end() && yopn.find(x0)!=yopn.end()) { sovlp.insert(x0); } } void insy(ll x0) { if (yopn.find(x0)==yopn.end()) { yopn[x0]=0; } yopn[x0]++; if (xopn.find(x0)!=xopn.end() && yopn.find(x0)!=yopn.end()) { sovlp.insert(x0); } } void delx(ll x0) { xopn[x0]--; if (xopn[x0]==0) { xopn.erase(xopn.find(x0)); if (sovlp.find(x0)!=sovlp.end()) { sovlp.erase(sovlp.find(x0)); } } } void dely(ll x0) { yopn[x0]--; if (yopn[x0]==0) { yopn.erase(yopn.find(x0)); if (sovlp.find(x0)!=sovlp.end()) { sovlp.erase(sovlp.find(x0)); } } } vector<int> ucs(vector<int> A, vector<int> B) { xopn.clear(); yopn.clear(); sovlp.clear(); xblk.clear(); yblk.clear(); vi fail = {-1}; vi ans; ll N = A.size(); ll M = B.size(); vector<ll> posa[Nm]; //posa[val] -> locations of val in order vector<ll> posb[Nm]; set<ll> rpa[Nm]; //remaining positions of val set<ll> rpb[Nm]; ll FLEN = 0; ll CLEN = 0; for (ll i=0;i<N;i++) { posa[A[i]].push_back(i); rpa[A[i]].insert(i); } for (ll i=0;i<M;i++) { posb[B[i]].push_back(i); rpb[B[i]].insert(i); } vector<ll> fnum(Nm,0); vector<ll> cnum(Nm,0); for (ll x=0;x<Nm;x++) { fnum[x]=min((ll)posa[x].size(),(ll)posb[x].size()); } ll xprc = 0; ll yprc = 0; //min x/y not processsed (initially unlocked by algo) ll xcvr = 0; ll ycvr = 0; //min x,y not covered ("walked over" by algo) xblk.insert(N-1); yblk.insert(M-1); for (ll x=0;x<Nm;x++) { ll mn = min((ll)posa[x].size(),(ll)posb[x].size()); FLEN += mn; // if (mn>0) { // xblk.insert(posa[x][posa[x].size()-mn]); // yblk.insert(posb[x][posb[x].size()-mn]); // } for (ll d=((ll)posa[x].size()-mn);d<((ll)posa[x].size());d++) { xblk.insert(posa[x][d]); //cout << "x="<<x<<", posa trm="<<posa[x][d]<<"\n"; } for (ll d=((ll)posb[x].size()-mn);d<((ll)posb[x].size());d++) { yblk.insert(posb[x][d]); //cout << "x="<<x<<", posb trm="<<posb[x][d]<<"\n"; } } while (FLEN>CLEN) { //cout << "loop start\n"; //cout << "xblk: "<<(*(xblk.begin()))<<"\n"; //cout << "yblk: "<<(*(yblk.begin()))<<"\n"; while (xprc<=(*(xblk.begin()))) { insx(A[xprc]); xprc++; } while (yprc<=(*(yblk.begin()))) { insy(B[yprc]); yprc++; } //cout << "sovlp elems: \n"; // for (ll x0: sovlp) { // cout << x0 << "=solvp term\n"; // } if (sovlp.size()!=1) { return fail; } ll v0 = *(sovlp.begin()); ans.push_back(v0); CLEN++; ll xfc = *(rpa[v0].begin()); ll yfc = *(rpb[v0].begin()); //cout << "xfc="<<xfc<<", yfc="<<yfc<<"\n"; // if ((ll)fnum[v0]<(ll)(posb[v0].size()-posa[v0].size())) { // //modify this // if (yblk.find(posb[v0][fnum[v0]])!=yblk.end()) { // yblk.erase(yblk.find(posb[v0][fnum[v0]])); // } // // if ((ll)fnum[v0]<(ll)(posb[v0].size()-posa[v0].size()-1)) { // // yblk.insert(posb[v0][fnum[v0]+1]); // // } // } if (posb[v0].size()>posa[v0].size()) { if (yblk.find(posb[v0][(ll)posb[v0].size()-(ll)posa[v0].size()+cnum[v0]])!=yblk.end()) { yblk.erase(yblk.find(posb[v0][(ll)posb[v0].size()-(ll)posa[v0].size()+cnum[v0]])); } } // if ((ll)fnum[v0]<(ll)(posa[v0].size()-posb[v0].size())) { // if (xblk.find(posa[v0][fnum[v0]])!=xblk.end()) { // xblk.erase(xblk.find(posa[v0][fnum[v0]])); // } // // if ((ll)fnum[v0]<(ll)(posa[v0].size()-posb[v0].size()-1)) { // // xblk.insert(posa[v0][fnum[v0]+1]); // // } // } if (posa[v0].size()>posb[v0].size()) { //cout << "xidx = " <<((ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0])<<"\n"; //cout << "deleting x block at: "<<posa[v0][(ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0]]<<"\n"; if (xblk.find(posa[v0][(ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0]])!=xblk.end()) { xblk.erase(xblk.find(posa[v0][(ll)posa[v0].size()-(ll)posb[v0].size()+cnum[v0]])); } } cnum[v0]++; while (xcvr<=xfc) { if (xblk.find(xcvr)!=xblk.end()) { delx(A[xcvr]); rpa[A[xcvr]].erase(rpa[A[xcvr]].find(xcvr)); xblk.erase(xblk.find(xcvr)); } xcvr++; } while (ycvr<=yfc) { if (yblk.find(ycvr)!=yblk.end()) { dely(B[ycvr]); rpb[B[ycvr]].erase(rpb[B[ycvr]].find(ycvr)); yblk.erase(yblk.find(ycvr)); } ycvr++; } } return ans; }