oj.uz

Submission #528842

# Submission time Handle Problem Language Result Execution time Memory
528842 2022-02-21T15:02:14 Z Koosha_mv Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 263 ms 425584 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];
		}
	}
	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);
	}
	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--;
		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]<<" ";
}

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++)
......
   60 |   f(i,0,s.size()){
      |     ~~~~~~~~~~~~               
selling_rna.cpp:60:3: note: in expansion of macro 'f'
   60 |   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 176 ms 407408 KB Output is correct
2 Correct 175 ms 407384 KB Output is correct
3 Correct 175 ms 407360 KB Output is correct
4 Correct 182 ms 407620 KB Output is correct
5 Correct 174 ms 407396 KB Output is correct
6 Correct 176 ms 407368 KB Output is correct
7 Correct 175 ms 407480 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 414312 KB Output is correct
2 Correct 211 ms 414296 KB Output is correct
3 Correct 208 ms 414328 KB Output is correct
4 Correct 209 ms 414148 KB Output is correct
5 Correct 247 ms 420932 KB Output is correct
6 Correct 245 ms 420804 KB Output is correct
7 Correct 226 ms 415232 KB Output is correct
8 Correct 247 ms 425584 KB Output is correct
9 Correct 242 ms 424696 KB Output is correct
10 Correct 200 ms 413504 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 409716 KB Output is correct
2 Correct 195 ms 408992 KB Output is correct
3 Correct 202 ms 409496 KB Output is correct
4 Correct 194 ms 409024 KB Output is correct
5 Correct 192 ms 408896 KB Output is correct
6 Correct 201 ms 409216 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 407408 KB Output is correct
2 Correct 175 ms 407384 KB Output is correct
3 Correct 175 ms 407360 KB Output is correct
4 Correct 182 ms 407620 KB Output is correct
5 Correct 174 ms 407396 KB Output is correct
6 Correct 176 ms 407368 KB Output is correct
7 Correct 175 ms 407480 KB Output is correct
8 Correct 210 ms 414312 KB Output is correct
9 Correct 211 ms 414296 KB Output is correct
10 Correct 208 ms 414328 KB Output is correct
11 Correct 209 ms 414148 KB Output is correct
12 Correct 247 ms 420932 KB Output is correct
13 Correct 245 ms 420804 KB Output is correct
14 Correct 226 ms 415232 KB Output is correct
15 Correct 247 ms 425584 KB Output is correct
16 Correct 242 ms 424696 KB Output is correct
17 Correct 200 ms 413504 KB Output is correct
18 Correct 205 ms 409716 KB Output is correct
19 Correct 195 ms 408992 KB Output is correct
20 Correct 202 ms 409496 KB Output is correct
21 Correct 194 ms 409024 KB Output is correct
22 Correct 192 ms 408896 KB Output is correct
23 Correct 201 ms 409216 KB Output is correct
24 Correct 214 ms 414912 KB Output is correct
25 Correct 220 ms 416176 KB Output is correct
26 Correct 216 ms 414376 KB Output is correct
27 Correct 215 ms 414708 KB Output is correct
28 Correct 263 ms 419732 KB Output is correct
29 Correct 240 ms 411744 KB Output is correct