oj.uz

Submission #11545

# Submission time Handle Problem Language Result Execution time Memory
11545 2014-11-30T16:52:04 Z tncks0121 전선 연결하기 (GA9_wire) C++14
0 / 100
 284 ms 30376 KB 
#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;
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27340 KB Output is correct
2 Correct 0 ms 27340 KB Output is correct
3 Correct 4 ms 27340 KB Output is correct
4 Correct 0 ms 27340 KB Output is correct
5 Correct 0 ms 27340 KB Output is correct
6 Correct 4 ms 27340 KB Output is correct
7 Correct 8 ms 27340 KB Output is correct
8 Correct 4 ms 27340 KB Output is correct
9 Correct 0 ms 27340 KB Output is correct
10 Correct 4 ms 27340 KB Output is correct
11 Correct 4 ms 27340 KB Output is correct
12 Correct 4 ms 27340 KB Output is correct
13 Correct 0 ms 27340 KB Output is correct
14 Correct 4 ms 27340 KB Output is correct
15 Correct 0 ms 27340 KB Output is correct
16 Correct 0 ms 27340 KB Output is correct
17 Correct 8 ms 27340 KB Output is correct
18 Correct 4 ms 27340 KB Output is correct
19 Correct 0 ms 27340 KB Output is correct
20 Correct 4 ms 27340 KB Output is correct
21 Correct 4 ms 27340 KB Output is correct
22 Correct 4 ms 27340 KB Output is correct
23 Correct 4 ms 27340 KB Output is correct
24 Correct 4 ms 27340 KB Output is correct
25 Correct 4 ms 27340 KB Output is correct
26 Correct 0 ms 27340 KB Output is correct
27 Incorrect 0 ms 27340 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 27340 KB Output is correct
2 Correct 0 ms 27340 KB Output is correct
3 Correct 0 ms 27340 KB Output is correct
4 Incorrect 8 ms 27340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 27604 KB Output is correct
2 Correct 20 ms 27604 KB Output is correct
3 Incorrect 104 ms 29188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 284 ms 30376 KB Output isn't correct
2 Halted 0 ms 0 KB -