oj.uz

Submission #11543

# Submission time Handle Problem Language Result Execution time Memory
11543 2014-11-30T15:37:00 Z tncks0121 전선 연결하기 (GA9_wire) C++14
0 / 100
 1000 ms 31412 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) {
    upd(tree1, L[v], 0);
    upd(tree2, R[v], -(int)1e7);
    if (used[v]) return;
    que.push(v); res[v] = r; used[v] = true;
}
int tmp[N_], tn;

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;
            
            tn = 0;
            
            // 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]); tmp[tn++] = A[r];
            }
            
            // 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]); tmp[tn++] = A[l];
            }
            
            for(int j = 0; j < tn; j++) {
                int i = tmp[j];
                upd(tree1, L[i], R[i]);
                upd(tree2, R[i], -L[i]);
            }
            
            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 0 ms 28512 KB Output is correct
2 Correct 8 ms 28512 KB Output is correct
3 Correct 0 ms 28512 KB Output is correct
4 Correct 0 ms 28512 KB Output is correct
5 Correct 0 ms 28512 KB Output is correct
6 Correct 4 ms 28512 KB Output is correct
7 Correct 0 ms 28512 KB Output is correct
8 Correct 0 ms 28512 KB Output is correct
9 Correct 0 ms 28512 KB Output is correct
10 Correct 4 ms 28512 KB Output is correct
11 Correct 4 ms 28512 KB Output is correct
12 Correct 0 ms 28512 KB Output is correct
13 Correct 8 ms 28512 KB Output is correct
14 Correct 0 ms 28512 KB Output is correct
15 Correct 0 ms 28512 KB Output is correct
16 Correct 0 ms 28512 KB Output is correct
17 Correct 0 ms 28512 KB Output is correct
18 Correct 0 ms 28512 KB Output is correct
19 Correct 0 ms 28512 KB Output is correct
20 Correct 0 ms 28512 KB Output is correct
21 Correct 0 ms 28512 KB Output is correct
22 Correct 0 ms 28512 KB Output is correct
23 Correct 0 ms 28512 KB Output is correct
24 Correct 4 ms 28512 KB Output is correct
25 Correct 0 ms 28512 KB Output is correct
26 Correct 0 ms 28512 KB Output is correct
27 Incorrect 4 ms 28512 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 28512 KB Output is correct
2 Correct 4 ms 28512 KB Output is correct
3 Correct 4 ms 28512 KB Output is correct
4 Incorrect 4 ms 28512 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 296 ms 28776 KB Output is correct
2 Correct 428 ms 28776 KB Output is correct
3 Execution timed out 1000 ms 30356 KB Program timed out
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 31412 KB Program timed out
2 Halted 0 ms 0 KB -