oj.uz

Submission #13495

# Submission time Handle Problem Language Result Execution time Memory
13495 2015-02-22T02:31:35 Z tncks0121 전선 연결하기 (GA9_wire) C++14
100 / 100
 536 ms 42936 KB 
#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;
 
void IMPOSSIBLE() {
    puts("IMPOSSIBLE");
    exit(0);
}
 
 
const int N_ = 300500;
const int LEAF = 1<<20;
const int TSZ = LEAF + LEAF + 3;
 
int N, A[N_ + N_];
bool used[N_];
int L[N_], R[N_];
 
struct segtree {
    int tree[TSZ];
    int type;
     
    segtree (int type): type(type) {
        if(type == 1) fill(tree, tree + TSZ, -987654321);
        if(type == 2) fill(tree, tree + TSZ, +987654321);
        if(type == 3) fill(tree, tree + TSZ, 0);
    }
     
    int func (int a, int b) {
        switch(type) {
            case 1: return max(a, b);
            case 2: return min(a, b);
            case 3: return a + b;
        }
        return -1;
    }
     
    void update (int pos, int val) {
        tree[pos += LEAF] = val;
        while(pos >>= 1) tree[pos] = func(tree[pos+pos], tree[pos+pos+1]);
    }
     
    int query (int l, int r) {
        int ret = -1987654321;
        bool wr = false;
        l += LEAF; r += LEAF;
        while(l <= r) {
            if((l & 1) == 1) ret = wr ? func(ret, tree[l]) : tree[l], wr = true;
            if((r & 1) == 0) ret = wr ? func(ret, tree[r]) : tree[r], wr = true;
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }
        return ret;
    }
     
    // for type 3
    int kth (int k) {
        if(type != 3) return -1;
        int nd = 1;
        while(nd < LEAF) {
            if(tree[nd + nd] <= k) {
                nd = nd + nd;
            }else {
                k -= tree[nd + nd];
                nd = nd + nd + 1;
            }
        }
        return nd - LEAF;
    }
};
 
segtree tree1(1), tree2(2), tree3(3);
 
/*
        1
    2       3
  4   5   6   7
 8 9 0 1 2 3 4 5
  
  
        2
    1       1
  1   0   1   0
 0 1 0 0 0 1 0 0
 */
 
queue<int> cand, que;
vector<int> inside[N_];
stack<int> stk;
 
int res[N_ + N_];
 
void que_push(int v, int r = 1) {
    if (used[v]) return;
    que.push(v); res[v] = r; used[v] = true;
    tree1.update (L[v], -987654321);
    tree2.update (R[v], +987654321);
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
     
    scanf("%d", &N);
    for(int i = 1; i <= N+N; i++) {
        scanf("%d", A+i);
        if(L[A[i]] == 0) L[A[i]] = i; else R[A[i]] = i;
    }
     
    for(int i = 1; i <= N; i++) {
        tree1.update (L[i], R[i]);
        tree2.update (R[i], L[i]);
    }
     
    for(int i = 1; i <= N+N; i++) {
        int a = A[i];
        if(L[a] == i) {
            int t = tree3.query(1, R[a]);
            if(tree3.tree[1] == t) cand.push(a);
            else inside[A[tree3.kth (t + 1)]].push_back(a);
            tree3.update (R[a], 0);
        }else {
            tree3.update (R[a], 1);
        }
    }
     
    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 = tree1.query(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 = tree2.query(R[u], N + N)) <= N + N;) {
                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 <= N + N; i++) if (res[A[i]] == cur) {
            if (!used[A[i]]) {
                used[A[i]] = true;
                stk.push(A[i]);
            }
            else {
                if (stk.top() != A[i]) IMPOSSIBLE();
                stk.pop();
            }
        }
    }
     
    for (int i = 1; i <= N + N; i++) printf("%c", res[A[i]] == 1 ? '^' : 'v');
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 40540 KB Output is correct
2 Correct 4 ms 40540 KB Output is correct
3 Correct 10 ms 40540 KB Output is correct
4 Correct 3 ms 40540 KB Output is correct
5 Correct 10 ms 40540 KB Output is correct
6 Correct 0 ms 40540 KB Output is correct
7 Correct 5 ms 40540 KB Output is correct
8 Correct 10 ms 40540 KB Output is correct
9 Correct 0 ms 40540 KB Output is correct
10 Correct 0 ms 40540 KB Output is correct
11 Correct 0 ms 40540 KB Output is correct
12 Correct 3 ms 40540 KB Output is correct
13 Correct 3 ms 40540 KB Output is correct
14 Correct 10 ms 40540 KB Output is correct
15 Correct 0 ms 40540 KB Output is correct
16 Correct 0 ms 40540 KB Output is correct
17 Correct 3 ms 40540 KB Output is correct
18 Correct 0 ms 40540 KB Output is correct
19 Correct 0 ms 40540 KB Output is correct
20 Correct 3 ms 40540 KB Output is correct
21 Correct 7 ms 40540 KB Output is correct
22 Correct 5 ms 40540 KB Output is correct
23 Correct 5 ms 40540 KB Output is correct
24 Correct 0 ms 40540 KB Output is correct
25 Correct 9 ms 40540 KB Output is correct
26 Correct 4 ms 40540 KB Output is correct
27 Correct 0 ms 40540 KB Output is correct
28 Correct 3 ms 40540 KB Output is correct
29 Correct 0 ms 40540 KB Output is correct
30 Correct 0 ms 40540 KB Output is correct
31 Correct 0 ms 40540 KB Output is correct
32 Correct 0 ms 40540 KB Output is correct
33 Correct 5 ms 40540 KB Output is correct
34 Correct 0 ms 40540 KB Output is correct
35 Correct 3 ms 40540 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 40540 KB Output is correct
2 Correct 11 ms 40540 KB Output is correct
3 Correct 3 ms 40540 KB Output is correct
4 Correct 7 ms 40540 KB Output is correct
5 Correct 10 ms 40540 KB Output is correct
6 Correct 4 ms 40540 KB Output is correct
7 Correct 10 ms 40540 KB Output is correct
8 Correct 10 ms 40540 KB Output is correct
9 Correct 7 ms 40540 KB Output is correct
10 Correct 10 ms 40540 KB Output is correct
11 Correct 10 ms 40540 KB Output is correct
12 Correct 5 ms 40540 KB Output is correct
13 Correct 8 ms 40540 KB Output is correct
14 Correct 3 ms 40540 KB Output is correct
15 Correct 5 ms 40540 KB Output is correct
16 Correct 4 ms 40540 KB Output is correct
17 Correct 11 ms 40540 KB Output is correct
18 Correct 0 ms 40540 KB Output is correct
19 Correct 10 ms 40540 KB Output is correct
20 Correct 5 ms 40540 KB Output is correct
21 Correct 11 ms 40540 KB Output is correct
22 Correct 11 ms 40540 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 40540 KB Output is correct
2 Correct 24 ms 40540 KB Output is correct
3 Correct 84 ms 40932 KB Output is correct
4 Correct 123 ms 40804 KB Output is correct
5 Correct 95 ms 40804 KB Output is correct
6 Correct 68 ms 40672 KB Output is correct
7 Correct 103 ms 40804 KB Output is correct
8 Correct 12 ms 40540 KB Output is correct
9 Correct 20 ms 40540 KB Output is correct
10 Correct 70 ms 40804 KB Output is correct
11 Correct 86 ms 40804 KB Output is correct
12 Correct 90 ms 40672 KB Output is correct
13 Correct 98 ms 40800 KB Output is correct
14 Correct 93 ms 40804 KB Output is correct
15 Correct 108 ms 40804 KB Output is correct
16 Correct 31 ms 40540 KB Output is correct
17 Correct 22 ms 40540 KB Output is correct
18 Correct 77 ms 40932 KB Output is correct
19 Correct 83 ms 40804 KB Output is correct
20 Correct 148 ms 40936 KB Output is correct
21 Correct 117 ms 40804 KB Output is correct
22 Correct 123 ms 40804 KB Output is correct
23 Correct 170 ms 40936 KB Output is correct
24 Correct 159 ms 40936 KB Output is correct
25 Correct 161 ms 40936 KB Output is correct
26 Correct 139 ms 40936 KB Output is correct
27 Correct 135 ms 41332 KB Output is correct
28 Correct 164 ms 41332 KB Output is correct
29 Correct 142 ms 41332 KB Output is correct
30 Correct 153 ms 41332 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 41200 KB Output is correct
2 Correct 358 ms 41460 KB Output is correct
3 Correct 234 ms 41200 KB Output is correct
4 Correct 331 ms 41332 KB Output is correct
5 Correct 394 ms 41484 KB Output is correct
6 Correct 524 ms 41876 KB Output is correct
7 Correct 502 ms 41880 KB Output is correct
8 Correct 375 ms 41484 KB Output is correct
9 Correct 248 ms 41200 KB Output is correct
10 Correct 262 ms 41332 KB Output is correct
11 Correct 341 ms 41484 KB Output is correct
12 Correct 265 ms 41200 KB Output is correct
13 Correct 517 ms 41880 KB Output is correct
14 Correct 500 ms 41748 KB Output is correct
15 Correct 268 ms 41332 KB Output is correct
16 Correct 236 ms 41200 KB Output is correct
17 Correct 288 ms 41200 KB Output is correct
18 Correct 252 ms 41200 KB Output is correct
19 Correct 357 ms 41484 KB Output is correct
20 Correct 536 ms 41880 KB Output is correct
21 Correct 502 ms 41748 KB Output is correct
22 Correct 431 ms 42936 KB Output is correct
23 Correct 509 ms 42936 KB Output is correct
24 Correct 447 ms 42936 KB Output is correct
25 Correct 469 ms 42936 KB Output is correct