Submission #11546

#	Time	Username	Problem	Language	Result	Execution time	Memory
11546		tncks0121	전선 연결하기 (GA9_wire)	C++14	100 / 100	760 ms	52668 KiB

wire

#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("IMPOSSIBLE");
    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;
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 37 / 37
• Subtask 4: 39 / 39