This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stack>
#include <memory.h>
#include <assert.h>
#include <stdlib.h>
#include <algorithm>
#include <set>
#include <queue>
#include <functional>
using namespace std;
const int N_ = 300500;
int N, X, A[N_ + N_];
bool used[N_];
int L[N_], R[N_];
vector<int> inside[N_];
queue<int> que;
queue<int> cand;
set<int> rpos;
stack<int> stk;
void INVALID() {
puts("INVALID");
exit(0);
}
int res[N_];
const int LEAF = 262144*4;
int tree1[N_ + N_ + LEAF];
int tree2[N_ + N_ + LEAF];
void upd(int *tree, int x, int v) {
tree[x += LEAF] = v;
while (x >>= 1) tree[x] = max(tree[x + x], tree[x + x + 1]);
}
int query(int *tree, int x, int y) {
x += LEAF; y += LEAF;
int ret = -(int)1e7;
while (x <= y) {
if ((x & 1) == 1) ret = max(ret, tree[x]);
if ((y & 1) == 0) ret = max(ret, tree[y]);
x = (x + 1) >> 1;
y = (y - 1) >> 1;
}
return ret;
}
void que_push(int v, int r = 1) {
if (used[v]) return;
que.push(v); res[v] = r; used[v] = true;
upd(tree1, L[v], 0);
upd(tree2, R[v], -(int)1e7);
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d", &N);
X = N + N;
for (int i = 1; i <= X; i++) {
scanf("%d", A + i);
if (!used[A[i]]) L[A[i]] = i; else R[A[i]] = i;
used[A[i]] = true;
}
fill(tree2, tree2 + LEAF + X + 10, -(int)1e7);
for (int i = 1; i <= N; i++) {
upd(tree1, L[i], R[i]);
upd(tree2, R[i], -L[i]);
}
memset(used, 0, sizeof used);
for (int i = 1; i <= X; i++) {
int a = A[i];
if (L[a] == i) {
set<int>::iterator it = rpos.lower_bound(R[a]);
if (it != rpos.end()) inside[A[*it]].push_back(a);
else cand.push(a);
rpos.insert(R[a]);
}
else {
rpos.erase(R[a]);
}
}
memset(used, 0, sizeof used);
int cnt = 0;
while (cnt < N) {
que_push(cand.front()); cand.pop();
while (!que.empty()) {
int u = que.front(); que.pop(); ++cnt;
// 1. L[x] < L[u] < R[x] < R[u]
for (int r; (r = query(tree1, 1, L[u])) > 0;) {
if (r < L[u]) break;
que_push(A[r], 3 - res[u]);
}
// 2. L[u] < L[x] < R[u] < R[x]
for (int l; (l = -query(tree2, R[u], X)) <= X;) {
if (R[u] < l) break;
que_push(A[l], 3 - res[u]);
}
for (int i = 0; i < inside[u].size(); i++) {
cand.push(inside[u][i]);
}
}
}
for (int cur = 1; cur <= 2; cur++) {
memset(used, 0, sizeof used);
while (!stk.empty()) stk.pop();
for (int i = 1; i <= X; i++) if (res[A[i]] == cur) {
if (!used[A[i]]) {
used[A[i]] = true;
stk.push(A[i]);
}
else {
if (stk.top() != A[i]) INVALID();
stk.pop();
}
}
}
for (int i = 1; i <= X; i++) printf("%c", res[A[i]] == 1 ? '^' : 'v');
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |