Submission #11558

#TimeUsernameProblemLanguageResultExecution timeMemory
11558tncks0121전선 연결하기 (GA9_wire)C++14
0 / 100
108 ms40200 KiB
#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; void INVALID() { puts("INVALID"); 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], +1); }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]) INVALID(); stk.pop(); } } } for (int i = 1; i <= N + N; i++) printf("%c", res[A[i]] == 1 ? '^' : 'v'); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...