답안 #13495 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13495	2015-02-22T02:31:35 Z	tncks0121	전선 연결하기 (GA9_wire)	C++14	100 / 100	536 ms	42936 KB

wire

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #13495

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 15.0 / 15.0

Subtask #3 37.0 / 37.0

Subtask #4 39.0 / 39.0

Subtask #1
9.0 / 9.0

Subtask #2
15.0 / 15.0

Subtask #3
37.0 / 37.0

Subtask #4
39.0 / 39.0