#include "hieroglyphs.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double if tight TL
using str = string;
using pi = pair<int,int>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vb = V<bool>;
using vpi = V<pi>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define pb push_back
#define ft front()
#define bk back()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const db PI = acos((db)-1);
mt19937 rng(0); // or mt19937_64
tcT> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
tcT, class U> T fstTrue(T lo, T hi, U f) {
++hi; assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
const int mx = 200005;
/**
* Description: 1D point update, range query where \texttt{cmb} is
* any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.
* Time: O(\log N)
* Source:
* http://codeforces.com/blog/entry/18051
* KACTL
* Verification: SPOJ Fenwick
*/
tcT> struct SegTree { // cmb(ID,b) = b
const T ID = -MOD; T cmb(T a, T b) { return max(a, b); }
int n; V<T> seg;
void init(int _n) { // upd, query also work if n = _n
for (n = 1; n < _n; ) n *= 2;
seg.assign(2*n,ID); }
void pull(int p) { seg[p] = cmb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // associative op on [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = cmb(ra,seg[l++]);
if (r&1) rb = cmb(seg[--r],rb);
}
return cmb(ra,rb);
}
/// int first_at_least(int lo, int val, int ind, int l, int r) { // if seg stores max across range
/// if (r < lo || val > seg[ind]) return -1;
/// if (l == r) return l;
/// int m = (l+r)/2;
/// int res = first_at_least(lo,val,2*ind,l,m); if (res != -1) return res;
/// return first_at_least(lo,val,2*ind+1,m+1,r);
/// }
};
vi ucs(vi A, vi B) {
int N = sz(A);
int M = sz(B);
vector<pair<int, vi>> special_As, special_Bs;
{
map<int, array<vi, 2>> at_poses;
for(int i = 0; i < N; i++){
at_poses[A[i]][0].pb(i);
}
for(int i = 0; i < M; i++){
at_poses[B[i]][1].pb(i);
}
for(auto u: at_poses){
if(sz(u.s[0]) == 0 || sz(u.s[1]) == 0) continue; //irrelevant
// cout << "u.s[0]: ";
// for(auto x: u.s[0]) cout << x << " ";
// cout << "\n";
// cout << "u.s[1]: ";
// for(auto x: u.s[1]) cout << x << " ";
// cout << "\n";
assert(sz(u.s[0]) == 1 || sz(u.s[1]) == 1);
if(sz(u.s[0]) == 1){
special_As.pb(mp(u.s[0][0], u.s[1]));
}
else{
special_Bs.pb(mp(u.s[1][0], u.s[0]));
}
}
}
int A_ind = 0;
int B_ind = 0;
vector<pair<char, int>> ord;
while(A_ind < sz(special_As) || B_ind < sz(special_Bs)){
if(A_ind == sz(special_As)){
ord.pb(mp('B', B_ind)); B_ind++; continue;
}
if(B_ind == sz(special_Bs)){
ord.pb(mp('A', A_ind)); A_ind++; continue;
}
bool A_before = special_As[A_ind].f < special_Bs[B_ind].s.bk && special_As[A_ind].s[0] < special_Bs[B_ind].f;
bool B_before = special_Bs[B_ind].f < special_As[A_ind].s.bk && special_Bs[B_ind].s[0] < special_As[A_ind].f;
if(A_before && B_before){
return vi{-1};
}
if(!A_before && !B_before){
return vi{-1};
}
if(A_before){
ord.pb(mp('A', A_ind)); A_ind++; continue;
}
assert(B_before);
ord.pb(mp('B', B_ind)); B_ind++; continue;
}
SegTree<int> A_max_to, B_max_to;
A_max_to.init(N);
B_max_to.init(M);
// for(int i = 0; i < sz(special_As); i++){
// A_max_to.upd(special_As[i].f, special_As[i].s.bk);
// }
// for(int i = 0; i < sz(special_Bs); i++){
// B_max_to.upd(special_Bs[i].f, special_Bs[i].s.bk);
// }
for(auto [side, ind]: ord){
if(side == 'A'){
if(B_max_to.query(special_As[ind].s[0], special_As[ind].s.bk) > special_As[ind].f){
return vi{-1};
}
A_max_to.upd(special_As[ind].f, special_As[ind].s.bk);
}
else{
if(A_max_to.query(special_Bs[ind].s[0], special_Bs[ind].s.bk) > special_Bs[ind].f){
return vi{-1};
}
B_max_to.upd(special_Bs[ind].f, special_Bs[ind].s.bk);
}
}
vi ans;
for(auto [side, ind]: ord){
if(side == 'A'){
ans.pb(A[special_As[ind].f]);
}
else{
ans.pb(B[special_Bs[ind].f]);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
452 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
448 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
6492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
6492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
452 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
