Submission #533368

#	Time	Username	Problem	Language	Result	Execution time	Memory
533368		GioChkhaidze	Floppy (RMI20_floppy)	C++14	100 / 100	139 ms	18000 KiB

floppy

#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 (stderr)

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 / 7
• Subtask 2: 21 / 21
• Subtask 3: 72 / 72