Submission #840061

#	Time	Username	Problem	Language	Result	Execution time	Memory
840061		Thanhs	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	172 ms	197336 KiB

selling_rna

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef stack<int> si;
typedef queue<int> qi;
typedef deque<int> di;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define endl '\n'
#define pb push_back
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define BACK(i,a,b) for(int i = a; i >= b; i--)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define fi first
#define se second
#define gcd __gcd
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))

const int MAXN=2e5+5;
const long long inf=1e18;
const int MOD=1e9+7;

struct node
{
	int l,r;
	node *nxt[4];
	vector<int> idx;
};

struct Op
{
	int x,y,idx;
	Op(int x,int y,int idx):x(x),y(y),idx(idx){}
	bool operator <(const Op& o) {return x<o.x;}
};

struct FT
{
	int n;
	vector<int> data;
	FT(int n):n(n),data(n+1){}
	void upd(int idx,int val) {for(;idx<=n;idx+=idx&-idx) data[idx]+=val;}
	int get(int idx) {int res=0; for(;idx;idx-=idx&-idx) res+=data[idx]; return res;}
};

array<int,2> points[MAXN];
int n,q,ans[MAXN],enc[256],cc;
node *root1=new node();
node *root2=new node();

void add(string &s,int idx)
{
	node *cur=root1;
	for(char c:s)
	{
		int ch=enc[(int)c];
		if(!cur->nxt[ch]) cur->nxt[ch]=new node();
		cur=cur->nxt[ch];
	}
	cur->idx.emplace_back(idx);
	reverse(s.begin(),s.end());
	cur=root2;
	for(char c:s)
	{
		int ch=enc[(int)c];
		if(!cur->nxt[ch]) cur->nxt[ch]=new node();
		cur=cur->nxt[ch];
	}
	cur->idx.emplace_back(idx);
}

void dfs(node *cur,int idx)
{
	cur->l=cc;
	for(int val:cur->idx) points[val][idx]=cc++;
	FOR(i,0,3) if(cur->nxt[i]) dfs(cur->nxt[i],idx);
	cur->r=cc-1;
}

pii get(string &s,node *cur)
{
	for(char c:s)
	{
		int ch=enc[(int)c];
		if(!cur->nxt[ch]) return {-1,-1};
		cur=cur->nxt[ch];
	}
	return {cur->l,cur->r};
}

signed main()
{
	fastIO
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	enc['A']=0; enc['C']=1; enc['G']=2; enc['U']=3;
	cin>>n>>q;
	FOR(i,1,n)
	{
		string s; cin>>s;
		add(s,i);
	}
	cc=1; dfs(root1,0);
	cc=1; dfs(root2,1);
	sort(points+1,points+n+1);
	vector<Op> op;
	auto addrange = [&](int x1,int x2,int y1,int y2,int idx) -> void
	{
		op.emplace_back(x2,y2,idx);
		op.emplace_back(x1-1,y2,-idx);
		op.emplace_back(x2,y1-1,-idx);
		op.emplace_back(x1-1,y1-1,idx);
	};
	FOR(i,1,q)
	{
		string pfx,sfx;
		cin>>pfx>>sfx;
		reverse(sfx.begin(),sfx.end());
		pii x=get(pfx,root1);
		pii y=get(sfx,root2);
		if(x.fi==-1||y.fi==-1) continue;
		addrange(x.fi,x.se,y.fi,y.se,i);
	}
	sort(op.begin(),op.end());
	FT fw(n);
	int ptr=1;
	for(Op t:op)
	{
		int x=t.x,y=t.y,idx=t.idx;
		while(ptr<=n&&points[ptr][0]<=x) fw.upd(points[ptr++][1],1);
		ans[abs(idx)]+=fw.get(y)*(idx>0?1:-1);
	}
	FOR(i,1,q) cout<<ans[i]<<endl;
}

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