oj.uz

답안 #533368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533368 2022-03-05T17:54:15 Z GioChkhaidze Floppy (RMI20_floppy) C++14
100 / 100
 139 ms 18000 KB 
#include <bits/stdc++.h>
#include "floppy.h"

using namespace std;

const int Nn = 2e5 + 5;

string s;
int n, tr, root, a[Nn], T[Nn], L[Nn], R[Nn];
int depth, dep[Nn], P[Nn][22], idx[Nn];
int Lc[Nn], Rc[Nn];

inline void dfs(int x) {
	if (Lc[x] != -1) 
		s += '1', dfs(Lc[x]);
			else 
		s += '0';
	
	if (Rc[x] != -1) 
		s += '1', dfs(Rc[x]);
			else 
		s += '0';
}

void read_array(int subtask_id, const vector<int> &v) {
    n = v.size();
    for (int i = 0; i < n; ++i) {
    	Lc[i + 1] = Rc[i + 1] = -1;
		a[i + 1] = v[i];
	}
	
	a[0] = 1e9 + 1;
	deque < int > dql;
	dql.push_back(0);
	for (int i = 1; i <= n; ++i) {
		while (a[dql.back()] < a[i])	
			dql.pop_back();
		L[i] = dql.back();
		dql.push_back(i);
	}

	a[n + 1] = 1e9 + 1;
	deque < int > dqr;
	dqr.push_back(n + 1);
	for (int i = n; i >= 1; --i) {
		while (a[dqr.back()] < a[i])	
			dqr.pop_back();
		R[i] = dqr.back();
		dqr.push_back(i);
	}

	
	for (int i = 1; i <= n; ++i) {
		if (L[i] == 0 && R[i] == n + 1) {
			root = i;
		}
	}
	
	for (int i = 1; i <= n; ++i) {
		if (L[i] != 0) {
			if (Rc[L[i]] == -1 || a[Rc[L[i]]] < a[i]) {
				Rc[L[i]] = i;
			}
		}
		
		if (R[i] != n + 1) {
			if (Lc[R[i]] == -1 || a[Lc[R[i]]] < a[i]) {
				Lc[R[i]] = i;
			}
		} 
	}
	
	dfs(root);
    save_to_floppy(s);
    return ;
}

inline int LCA(int a, int b) {
	if (a == b) return a;
	if (dep[a] < dep[b]) swap(a, b);
	for (int i = 19; i >= 0; --i) 
		if (dep[P[a][i]] >= dep[b]) a = P[a][i];
	if (a == b) return a;
	for (int i = 19; i >= 0; --i) 
		if (P[a][i] != P[b][i]) a = P[a][i], b = P[b][i];
	return P[a][0];
}

inline void ufs(int x, int l, int r) {
	idx[x] = r - (Rc[x] - Lc[x]);
	dep[idx[x]] = ++depth;
	if (L[x]) {
		ufs(L[x], l, r - (Rc[x] - Lc[x] + 1));
		P[idx[L[x]]][0] = idx[x];
	}
	
	if (R[x]) {
		ufs(R[x], l + (Lc[x] - x + 1), r);	
		P[idx[R[x]]][0] = idx[x];
	}
	--depth;
}

vector < int > solve_queries(int subtask_id, int N, const string &bits, const vector<int> &a, const vector<int> &b) {
    n = N;
    tr = 1;
	s = bits;
    int q = a.size();
    deque < int > dq;
    dq.push_back(tr);
    for (int i = 1; i <= n; ++i) {
    	Lc[i] = Rc[i] = 0;
		L[i] = R[i] = 0;
	}
    for (int i = 0; i < s.size(); ++i) {
    	if (!T[dq.back()]) {
    		T[dq.back()] = 1;
			if (s[i] == '1') {
    			L[dq.back()] = ++tr;
				dq.push_back(tr);
			}
				else {
				Lc[dq.back()] = tr;		
			}		
		}
			else
		if (T[dq.back()]) {
			T[dq.back()] = 2;
			if (s[i] == '1') {
    			R[dq.back()] = ++tr;
				dq.push_back(tr);
			}	
				else {
				while (dq.size() && T[dq.back()] == 2) {
					Rc[dq.back()] = tr;
					dq.pop_back();
				}
				if (dq.size() && T[dq.back()] == 1) {
					Lc[dq.back()] = tr;
				}
			}
		}
 	}
	
	ufs(1, 0, n);
	P[idx[1]][0] = idx[1];
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i <= n; ++i) 
			P[i][j] = P[P[i][j - 1]][j - 1];
	
	vector < int > answers;
	for (int i = 0; i < q; ++i) {
		answers.push_back(LCA(a[i] + 1, b[i] + 1) - 1);
	}
	
    return answers;
}

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int i = 0; i < s.size(); ++i) {
      |                     ~~^~~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 2 ms 776 KB Output is correct
3 Correct 2 ms 804 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 3 ms 792 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 4512 KB Output is correct
2 Correct 30 ms 4536 KB Output is correct
3 Correct 28 ms 4936 KB Output is correct
4 Correct 28 ms 4772 KB Output is correct
5 Correct 30 ms 4592 KB Output is correct

Subtask #3
72.0 / 72.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 16972 KB Output is correct
2 Correct 139 ms 16948 KB Output is correct
3 Correct 129 ms 18000 KB Output is correct
4 Correct 111 ms 17912 KB Output is correct
5 Correct 112 ms 17048 KB Output is correct