Submission #1181661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181661		boclobanchat	Floppy (RMI20_floppy)	C++20	0 / 100	63 ms	9288 KiB

floppy

#include"floppy.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
int getlog(long long n) { return 63-__builtin_clzll(n); }
void read_array(int subtask_id,const vector<int> &v)
{
	string s;
	int n=v.size();
	vector<int> val=v,lay(n);
	vector< vector<ii> > sp(22);
	sort(val.begin(),val.end());
	for(int i=0;(1<<i)<=n;i++) sp[i].resize(n);
	for(int i=0;i<n;i++) sp[0][i]={lower_bound(val.begin(),val.end(),v[i])-val.begin(),i};
	for(int i=1;(1<<i)<=n;i++) for(int j=0;j<=n-(1<<i);j++) sp[i][j]=max(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
	queue<ii> Q;
	Q.push({0,n-1});
	while(!Q.empty())
	{
		ii a=Q.front();
		Q.pop();
		int lg=getlog(a.se-a.fi+1),mxpos=max(sp[lg][a.fi],sp[lg][a.se-(1<<lg)+1]).se;
		ii b={a.fi,mxpos-1},c={mxpos+1,a.se};
		if(b.fi<=b.se)
		{
			int lg2=getlog(b.se-b.fi+1),mxpos2=max(sp[lg2][b.fi],sp[lg2][b.se-(1<<lg2)+1]).se;
			Q.push(b),s+='1';
		}
		else s+='0';
		if(c.fi<=c.se)
		{
			int lg2=getlog(c.se-c.fi+1),mxpos2=max(sp[lg2][c.fi],sp[lg2][c.se-(1<<lg2)+1]).se;
			Q.push(c),s+='1';
		}
		else s+='0';
	}
    save_to_floppy(s);
}
vector<int> solve_queries(int subtask_id,int n,const string &s,const vector<int> &a,const vector<int> &b)
{
	stack<int> st;
	st.push(0);
	vector<int> ans,lay(n);
	int val=0,pos=0,cnt=0,it=0;
	while(!st.empty())
	{
		int a=st.top();
		st.pop();
		if(a==-1) lay[pos++]=cnt;
		else if(a==-2) cnt--;
		else
		{
			bool lt=s[it*2]-'0',rt=s[it*2+1]-'0';
			cnt++,it++;
			st.push(-2);
			if(rt) st.push(0);
			st.push(-1);
			if(lt) st.push(0);
		}
	}
	vector< vector<ii> > sp(22);
	for(int i=0;(1<<i)<=n;i++) sp[i].resize(n);
	for(int i=0;i<n;i++) sp[0][i]={lay[i],i};
	for(int i=1;(1<<i)<=n;i++) for(int j=0;j<=n-(1<<i);j++) sp[i][j]=min(sp[i-1][j],sp[i-1][j+(1<<(i-1))]);
	for(int i=0;i<a.size();i++)
	{
		int l=a[i],r=b[i],lg=getlog(r-l+1);
		ans.push_back(min(sp[lg][l],sp[lg][r-(1<<lg)+1]).se);
	}
    return ans;
}

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