제출 #1225443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225443		MuhammadSaram	Floppy (RMI20_floppy)	C++20	0 / 100	20 ms	4164 KiB

floppy

#include <bits/stdc++.h>
// #include "floppy.h"

using namespace std;

const int M = 40001, lg = 16;

int maxx[M][lg],a[M],par[M][lg],ch[M][2],id[M],nd[M],ind[M],dep[M],t;
string s;

int get(int l,int r)
{
	int b=31-__builtin_clz(r-l);
	if (a[maxx[l][b]]>a[maxx[r-(1<<b)][b]])
		return maxx[l][b];
	return maxx[r-(1<<b)][b];
}

void f(int l,int r)
{
	int id=get(l,r);
	if (id!=l) s+='1',f(l,id);
	else s+='0';
	if (id!=r-1) s+='1',f(id+1,r);
	else s+='0';
}

void read_array(int subtask_id, const vector<int> &A)
{
	int n=A.size();
	for (int i=0;i<n;i++) a[i]=A[i],maxx[i][0]=i;
	for (int p=1;p<lg;p++)
		for (int i=0;i+(1<<p)<=n;i++)
		{
			maxx[i][p]=maxx[i][p-1];
			if (a[maxx[i][p-1]]<a[maxx[i+(1<<p-1)][p-1]])
				maxx[i][p]=maxx[i+(1<<p-1)][p-1];
		}
	f(0,n);
	// save_to_floppy(s);
}

void dfs(int u)
{
	if (ch[u][0])
		dfs(ch[u][0]);
	ind[u]=t,nd[t++]=u;
	if (ch[u][1])
		dfs(ch[u][1]);
}

int lca(int u,int v)
{
	if (dep[u]>dep[v]) swap(u,v);
	for (int p=lg-1;p>=0;p--)
		if (dep[v]-dep[u]>=(1<<p))
			v=par[v][p];
	if (u==v) return u;
	for (int p=lg-1;p>=0;p--)
		if (par[u][p]!=par[v][p])
			u=par[u][p],v=par[v][p];
	return par[u][0];
}

vector<int> solve_queries(int subtask_id, int n,
        const string &s,
        const vector<int> &a, const vector<int> &b) {
    vector<int> ans;
    int r=1,nx=2;
    for (int i=0;i<2*n;i++)
    {
  		while (id[r]==2)
  			r=par[r][0];
    	if (s[i]=='1')
    		ch[r][id[r]++]=nx,par[nx][0]=r,dep[nx]=dep[r]+1,r=nx++;
    	else
    		id[r]++;
    }
    dfs(1);
    for (int p=1;p<lg;p++)
    	for (int i=0;i<n;i++)
    		par[i][p]=par[par[i][p-1]][p-1];
    for (int i=0;i<a.size();i++)
    	ans.push_back(ind[lca(nd[a[i]],nd[b[i]])]);
    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 21
• Subtask 3: 0 / 72