oj.uz

Submission #528841

# Submission time Handle Problem Language Result Execution time Memory
528841 2022-02-21T15:01:06 Z Koosha_mv Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 300 ms 431272 KB 
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2e6+99,S=4;

int n,m,ans[N],L[N],R[N],fenwik[N];
string s[N],t[N],a[N],b[N];
vector<int> vec[N];
vector<pair<int,int>> Q[N];

void add(int x, int val=1){ for(x++;x<N;x+=x&-x) fenwik[x]+=val; }
int get(int x) { int res=0; for (x++;x>0;x-=x&-x) res+=fenwik[x]; return res; }

int g(char c){
	if(c=='A') return 0;
	if(c=='U') return 1;
	if(c=='G') return 2;
	if(c=='C') return 3;
}
struct trie{
	int cnt,Time,st[N],ft[N],child[N][S];
	trie(){
		Time=cnt=1;
		f(i,0,N) f(j,0,S) child[i][j]=0;
	}
	void add(string s){
		int now=1;
		f(i,0,s.size()){
			int nxt=g(s[i]);
			if(!child[now][nxt]) child[now][nxt]=++cnt;
			now=child[now][nxt];
			//eror(now);
		}
	}
	void dfs(int u=1){
		st[u]=Time++;
		f(i,0,S) if(child[u][i]) dfs(child[u][i]);
		ft[u]=Time;
	}
	pair<int,int> find(string s){
		int now=1;
		f(i,0,s.size()){
			int nxt=g(s[i]);
			if(!child[now][nxt]) return {st[now],ft[now]};
			now=child[now][nxt];
		}
		return {st[now],ft[now]};
	}
} t1,t2;

int main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>m;
	f(i,0,n) cin>>s[i],t[i]=s[i],reverse(all(t[i]));
	f(i,0,m){
		cin>>a[i]>>b[i];
		reverse(all(b[i]));
		t1.add(a[i]);
		t2.add(b[i]);
	}
	t1.dfs();
	t2.dfs();
	f(i,0,n){
		vec[t1.find(s[i]).F].pb(t2.find(t[i]).F);
		//cout<<t1.find(s[i]).F<<" - "<<t2.find(t[i]).F<<endl;
	}
	f(i,0,m){
		pair<int,int> e1=t1.find(a[i]),e2=t2.find(b[i]);
		e1.F--,e1.S--;
		e2.F--,e2.S--;
		//erorp(e1);
		//erorp(e2);
		L[i]=e2.F;
		R[i]=e2.S;
		Q[e1.F].pb({i,-1});
		Q[e1.S].pb({i,+1});
	}
	f(i,0,N){
		for(auto x : vec[i]) add(x);
		for(auto p : Q[i]){
			int res=get(R[p.F])-get(L[p.F]);
			ans[p.F]+=res*p.S;
		}
	}
	f(i,0,m) cout<<ans[i]<<" ";
}
/*
2 1
GCGCUACCCCAACACAAGGCAAGAUAUA
GCGCUACCCCAACACAAGGCAAGAUGGUC
GCGCUACCC A


GCGCUACCCC AC
GCG C
GCGC A
G G
G C
G GGA
*/

Compilation message

selling_rna.cpp: In member function 'void trie::add(std::string)':
selling_rna.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   47 |   f(i,0,s.size()){
      |     ~~~~~~~~~~~~               
selling_rna.cpp:47:3: note: in expansion of macro 'f'
   47 |   f(i,0,s.size()){
      |   ^
selling_rna.cpp: In member function 'std::pair<int, int> trie::find(std::string)':
selling_rna.cpp:8:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   61 |   f(i,0,s.size()){
      |     ~~~~~~~~~~~~               
selling_rna.cpp:61:3: note: in expansion of macro 'f'
   61 |   f(i,0,s.size()){
      |   ^
selling_rna.cpp: In function 'int g(char)':
selling_rna.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 407476 KB Output is correct
2 Correct 193 ms 407484 KB Output is correct
3 Correct 190 ms 407380 KB Output is correct
4 Correct 191 ms 407476 KB Output is correct
5 Correct 198 ms 407372 KB Output is correct
6 Correct 189 ms 407440 KB Output is correct
7 Correct 196 ms 407412 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 417728 KB Output is correct
2 Correct 226 ms 417860 KB Output is correct
3 Correct 225 ms 417944 KB Output is correct
4 Correct 231 ms 417800 KB Output is correct
5 Correct 257 ms 423292 KB Output is correct
6 Correct 261 ms 423096 KB Output is correct
7 Correct 245 ms 420412 KB Output is correct
8 Correct 271 ms 431272 KB Output is correct
9 Correct 267 ms 430556 KB Output is correct
10 Correct 219 ms 416756 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 409972 KB Output is correct
2 Correct 210 ms 409208 KB Output is correct
3 Correct 213 ms 409696 KB Output is correct
4 Correct 230 ms 409308 KB Output is correct
5 Correct 207 ms 409100 KB Output is correct
6 Correct 213 ms 409436 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 407476 KB Output is correct
2 Correct 193 ms 407484 KB Output is correct
3 Correct 190 ms 407380 KB Output is correct
4 Correct 191 ms 407476 KB Output is correct
5 Correct 198 ms 407372 KB Output is correct
6 Correct 189 ms 407440 KB Output is correct
7 Correct 196 ms 407412 KB Output is correct
8 Correct 229 ms 417728 KB Output is correct
9 Correct 226 ms 417860 KB Output is correct
10 Correct 225 ms 417944 KB Output is correct
11 Correct 231 ms 417800 KB Output is correct
12 Correct 257 ms 423292 KB Output is correct
13 Correct 261 ms 423096 KB Output is correct
14 Correct 245 ms 420412 KB Output is correct
15 Correct 271 ms 431272 KB Output is correct
16 Correct 267 ms 430556 KB Output is correct
17 Correct 219 ms 416756 KB Output is correct
18 Correct 213 ms 409972 KB Output is correct
19 Correct 210 ms 409208 KB Output is correct
20 Correct 213 ms 409696 KB Output is correct
21 Correct 230 ms 409308 KB Output is correct
22 Correct 207 ms 409100 KB Output is correct
23 Correct 213 ms 409436 KB Output is correct
24 Correct 232 ms 418744 KB Output is correct
25 Correct 242 ms 420344 KB Output is correct
26 Correct 232 ms 418432 KB Output is correct
27 Correct 238 ms 418804 KB Output is correct
28 Correct 300 ms 424144 KB Output is correct
29 Correct 259 ms 414916 KB Output is correct