oj.uz

Submission #202270

# Submission time Handle Problem Language Result Execution time Memory
202270 2020-02-15T01:15:03 Z Segtree Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 964 ms 56092 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 100010
string s[N],p[N],q[N];
ll a[N],b[N],c[N],d[N];
ll ys[N];
vector<ll> dat[2*N];
ll ret(ll c,ll d,ll k){
    return lower_bound(all(dat[k]),d)-lower_bound(all(dat[k]),c);
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<string,int> >v;
    rep(i,n){
	cin>>s[i];
    }
    rep(i,m)cin>>p[i]>>q[i];
    sort(s,s+n);
    
    rep(i,m){
	a[i]=lower_bound(s,s+n,p[i])-s;
	p[i][p[i].size()-1]++;
	b[i]=lower_bound(s,s+n,p[i])-s;
    }
    rep(i,n){
	rep(j,s[i].size()/2)swap(s[i][j],s[i][s[i].size()-1-j]);
	v.push_back(make_pair(s[i],i));
    }
    sort(v.begin(),v.end());
    rep(i,n)ys[v[i].second]=i;
    rep(i,n)s[i]=v[i].first;
    rep(i,m){
	rep(j,q[i].size()/2)swap(q[i][j],q[i][q[i].size()-1-j]);
	c[i]=lower_bound(s,s+n,q[i])-s;
	q[i][q[i].size()-1]++;
	d[i]=lower_bound(s,s+n,q[i])-s;
    }
    rep(i,n){
	for(ll x=i+N;x;x>>=1){
	    dat[x].push_back(ys[i]);
	}
    }
    rep(i,2*N)sort(dat[i].begin(),dat[i].end());
    rep(i,m){
	ll ans=0;
	ll l=a[i]+N,r=b[i]+N;
	for(;l<r;l>>=1,r>>=1){
	    if(l&1)ans+=ret(c[i],d[i],l++);
	    if(r&1)ans+=ret(c[i],d[i],--r);
	}
	cout<<ans<<endl;
    }
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:13:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
selling_rna.cpp:40:6:
  rep(j,s[i].size()/2)swap(s[i][j],s[i][s[i].size()-1-j]);
      ~~~~~~~~~~~~~~~           
selling_rna.cpp:40:2: note: in expansion of macro 'rep'
  rep(j,s[i].size()/2)swap(s[i][j],s[i][s[i].size()-1-j]);
  ^~~
selling_rna.cpp:13:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
selling_rna.cpp:47:6:
  rep(j,q[i].size()/2)swap(q[i][j],q[i][q[i].size()-1-j]);
      ~~~~~~~~~~~~~~~           
selling_rna.cpp:47:2: note: in expansion of macro 'rep'
  rep(j,q[i].size()/2)swap(q[i][j],q[i][q[i].size()-1-j]);
  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14456 KB Output is correct
6 Correct 15 ms 14460 KB Output is correct
7 Correct 14 ms 14456 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 23800 KB Output is correct
2 Correct 255 ms 24660 KB Output is correct
3 Correct 251 ms 24312 KB Output is correct
4 Correct 263 ms 24664 KB Output is correct
5 Correct 176 ms 21076 KB Output is correct
6 Correct 178 ms 21180 KB Output is correct
7 Correct 314 ms 24272 KB Output is correct
8 Correct 360 ms 25172 KB Output is correct
9 Correct 350 ms 25044 KB Output is correct
10 Correct 222 ms 22488 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 27996 KB Output is correct
2 Correct 178 ms 22504 KB Output is correct
3 Correct 241 ms 25340 KB Output is correct
4 Correct 185 ms 23652 KB Output is correct
5 Correct 176 ms 22508 KB Output is correct
6 Correct 220 ms 25188 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct
3 Correct 14 ms 14456 KB Output is correct
4 Correct 14 ms 14456 KB Output is correct
5 Correct 14 ms 14456 KB Output is correct
6 Correct 15 ms 14460 KB Output is correct
7 Correct 14 ms 14456 KB Output is correct
8 Correct 235 ms 23800 KB Output is correct
9 Correct 255 ms 24660 KB Output is correct
10 Correct 251 ms 24312 KB Output is correct
11 Correct 263 ms 24664 KB Output is correct
12 Correct 176 ms 21076 KB Output is correct
13 Correct 178 ms 21180 KB Output is correct
14 Correct 314 ms 24272 KB Output is correct
15 Correct 360 ms 25172 KB Output is correct
16 Correct 350 ms 25044 KB Output is correct
17 Correct 222 ms 22488 KB Output is correct
18 Correct 265 ms 27996 KB Output is correct
19 Correct 178 ms 22504 KB Output is correct
20 Correct 241 ms 25340 KB Output is correct
21 Correct 185 ms 23652 KB Output is correct
22 Correct 176 ms 22508 KB Output is correct
23 Correct 220 ms 25188 KB Output is correct
24 Correct 348 ms 30652 KB Output is correct
25 Correct 472 ms 32256 KB Output is correct
26 Correct 302 ms 30092 KB Output is correct
27 Correct 335 ms 30708 KB Output is correct
28 Correct 964 ms 56092 KB Output is correct
29 Correct 718 ms 44120 KB Output is correct