oj.uz

Submission #421314

# Submission time Handle Problem Language Result Execution time Memory
421314 2021-06-09T02:27:58 Z Focutai Floppy (RMI20_floppy) C++17
100 / 100
 125 ms 18200 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fast_IO ios::sync_with_stdio(false);
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define fir first
#define sec second
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
#include "floppy.h"

namespace Encode
{
	const int N=40005;
	int a[N],st[N][17],lg[N];
	int Max(int x,int y) {return a[x]>a[y]?x:y;}
	string ans;
	int query(int l,int r)
	{
		int t=lg[r-l+1];
		return Max(st[l][t],st[r-(1<<t)+1][t]);
	}
	void solve(int l,int r)
	{
		if(l==r) {ans+="00"; return ;}
		int mid=query(l,r);
//		printf("%d %d - %d\n",l,r,mid);
		if(l==mid) ans+="01",solve(mid+1,r);
		else if(r==mid) ans+="10",solve(l,mid-1);
		else ans+="11",solve(l,mid-1),solve(mid+1,r);
	}
	void Main(vector<int> _a)
	{
		for(int i=2;i<N;i++) lg[i]=lg[i/2]+1;
		int n=_a.size(); for(int i=0;i<n;i++) a[i]=_a[i];
		for(int i=0;i<n;i++) st[i][0]=i;
		for(int j=1;j<17;j++) for(int i=0;i+(1<<j)-1<n;i++) st[i][j]=Max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
//		for(int j=0;j<=2;j++) for(int i=0;i<n;i++) printf("%d%c",st[i][j]," \n"[i==n-1]);
		solve(0,n-1);
//		cout<<ans<<endl;
		save_to_floppy(ans);
	}
};
void read_array(int subtask_id, const std::vector<int> &v) {Encode::Main(v);}

namespace Decode
{
	const int N=40005;
	string str;
	int ls[N],rs[N],siz[N],id[N],rev[N],cnt,pos;
	int build()
	{
		int cur=++cnt; siz[cur]=1;
		int hl=str[pos++]-'0',hr=str[pos++]-'0';
		if(hl) ls[cur]=build(),siz[cur]+=siz[ls[cur]];
		if(hr) rs[cur]=build(),siz[cur]+=siz[rs[cur]];
		return cur;
	}
	int fa[N],dep[N],son[N],top[N];
	void dfs1(int u,int f,int pre)
	{
		id[u]=pre+siz[ls[u]],fa[u]=f,dep[u]=dep[f]+1;
		rev[id[u]]=u;
		if(ls[u])
		{
			dfs1(ls[u],u,pre);
			if(siz[ls[u]]>siz[son[u]]) son[u]=ls[u];
		}
		if(rs[u])
		{
			dfs1(rs[u],u,pre+siz[ls[u]]+1);
			if(siz[rs[u]]>siz[son[u]]) son[u]=rs[u];
		}
	}
	void dfs2(int u,int tp)
	{
		top[u]=tp;
		if(son[u]) dfs2(son[u],tp);
		if(ls[u]&&ls[u]!=son[u]) dfs2(ls[u],ls[u]);
		if(rs[u]&&rs[u]!=son[u]) dfs2(rs[u],rs[u]);
	}
	int lca(int u,int v)
	{
		while(top[u]!=top[v])
		{
			if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
			else v=fa[top[v]];
		}
		return dep[u]<dep[v]?u:v;
	}
	vector<int> Main(int n,string bits,vector<int> ql,vector<int> qr)
	{
		str=bits;
		build();
		dfs1(1,0,0),dfs2(1,1);
//		for(int i=1;i<=n;i++) printf("%d - %d %d\n",id[i],ls[i],rs[i]);
		int Q=ql.size(); vector<int> ans(Q);
		for(int i=0;i<Q;i++) ans[i]=id[lca(rev[ql[i]],rev[qr[i]])];
		return ans;
	}
};

std::vector<int> solve_queries(int subtask_id, int N, const std::string &bits, const std::vector<int> &a, const std::vector<int> &b)
{
	return Decode::Main(N,bits,a,b);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 928 KB Output is correct
2 Correct 3 ms 916 KB Output is correct
3 Correct 2 ms 924 KB Output is correct
4 Correct 2 ms 916 KB Output is correct
5 Correct 3 ms 912 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4604 KB Output is correct
2 Correct 27 ms 4616 KB Output is correct
3 Correct 26 ms 5068 KB Output is correct
4 Correct 26 ms 4888 KB Output is correct
5 Correct 27 ms 4704 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 16600 KB Output is correct
2 Correct 125 ms 16400 KB Output is correct
3 Correct 106 ms 18200 KB Output is correct
4 Correct 104 ms 17560 KB Output is correct
5 Correct 110 ms 16580 KB Output is correct