Submission #230914

#	Time	Username	Problem	Language	Result	Execution time	Memory
230914		arnold518	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	289 ms	180856 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e6;

char T[MAXN+10];

int N, M;
vector<int> A[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
int XS, YS;

struct Node
{
	int L, R;
	Node *chd[4];
	Node() : L(MAXN*2), R(0)
	{
		chd[0]=NULL; chd[1]=NULL; chd[2]=NULL; chd[3]=NULL;
	}
};

void update(Node *node, vector<int> &V, int it)
{
	if(it==V.size()) return;
	if(node->chd[V[it]]==NULL) node->chd[V[it]]=new Node();
	update(node->chd[V[it]], V, it+1);
}

int cnt=0;
void dfs(Node *node)
{
	int i, j;
	node->L=++cnt;
	for(i=0; i<4; i++)
	{
		if(node->chd[i]==NULL) continue;
		dfs(node->chd[i]);
	}
	node->R=cnt;
}

pii query(Node *node, vector<int> &V, int it)
{
	if(it==V.size()) return {node->L, node->R};
	if(node->chd[V[it]]==NULL) return {-1, -1};
	return query(node->chd[V[it]], V, it+1);
}

Node *root1, *root2;

struct Data
{
	int x, y1, y2, p;
	bool operator < (const Data &p) { return x<p.x; }
};
vector<Data> DV;

struct BIT
{
	vector<int> tree;
	BIT() : tree(MAXN+10) {}
	void update(int i) { for(; i<=YS; i+=(i&-i)) tree[i]++; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
	int query(int l, int r) { return query(r)-query(l-1); }
}bit;

int ans[MAXN+10];

int main()
{
	int i, j, k;

	scanf("%d%d", &N, &M);
	root1=new Node();
	root2=new Node();

	for(i=1; i<=N; i++)
	{
		scanf("%s", T);
		for(j=0; T[j]; j++)
		{
			if(T[j]=='A') A[i].push_back(0);
			if(T[j]=='G') A[i].push_back(1);
			if(T[j]=='C') A[i].push_back(2);
			if(T[j]=='U') A[i].push_back(3);
		}
		update(root1, A[i], 0);
		reverse(A[i].begin(), A[i].end());
		update(root2, A[i], 0);
		reverse(A[i].begin(), A[i].end());
	}

	cnt=0;
	dfs(root1);
	for(i=1; i<=N; i++)
	{
		pii t=query(root1, A[i], 0);
		X[i]=t.first;
	}
	XS=cnt;

	cnt=0;
	dfs(root2);
	for(i=1; i<=N; i++)
	{
		reverse(A[i].begin(), A[i].end());
		pii t=query(root2, A[i], 0);
		reverse(A[i].begin(), A[i].end());
		Y[i]=t.first;
	}
	YS=cnt;

	vector<pii> PV;
	for(i=1; i<=N; i++) PV.push_back({X[i], Y[i]});

	for(i=1; i<=M; i++)
	{
		vector<int> B, C;
		scanf("%s", T);
		for(j=0; T[j]; j++)
		{
			if(T[j]=='A') B.push_back(0);
			if(T[j]=='G') B.push_back(1);
			if(T[j]=='C') B.push_back(2);
			if(T[j]=='U') B.push_back(3);
		}

		scanf("%s", T);
		for(j=0; T[j]; j++)
		{
			if(T[j]=='A') C.push_back(0);
			if(T[j]=='G') C.push_back(1);
			if(T[j]=='C') C.push_back(2);
			if(T[j]=='U') C.push_back(3);
		}
		reverse(C.begin(), C.end());

		pii xr=query(root1, B, 0), yr=query(root2, C, 0);
		if(xr.first==-1 || yr.first==-1) continue;
		DV.push_back({xr.first-1, yr.first, yr.second, -i});
		DV.push_back({xr.second, yr.first, yr.second, i});
	}
	sort(DV.begin(), DV.end());
	sort(PV.begin(), PV.end());

	for(i=0, j=0, k=0; i<=XS; i++)
	{
		for(; j<PV.size() && PV[j].first==i; j++) bit.update(PV[j].second);
		for(; k<DV.size() && DV[k].x==i; k++)
		{
			int t=bit.query(DV[k].y1, DV[k].y2);
			if(DV[k].p>0) ans[DV[k].p]+=t;
			else ans[-DV[k].p]-=t;
		}
	}

	for(i=1; i<=M; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

selling_rna.cpp: In function 'void update(Node*, std::vector<int>&, int)':
selling_rna.cpp:29:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(it==V.size()) return;
     ~~^~~~~~~~~~
selling_rna.cpp: In function 'void dfs(Node*)':
selling_rna.cpp:37:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
selling_rna.cpp: In function 'pii query(Node*, std::vector<int>&, int)':
selling_rna.cpp:49:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(it==V.size()) return {node->L, node->R};
     ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:153:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<PV.size() && PV[j].first==i; j++) bit.update(PV[j].second);
         ~^~~~~~~~~~
selling_rna.cpp:154:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; k<DV.size() && DV[k].x==i; k++)
         ~^~~~~~~~~~
selling_rna.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", T);
   ~~~~~^~~~~~~~~
selling_rna.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", T);
   ~~~~~^~~~~~~~~
selling_rna.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", T);
   ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40