oj.uz

Submission #202269

# Submission time Handle Problem Language Result Execution time Memory
202269 2020-02-15T01:09:44 Z Segtree Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 349 ms 25428 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];
int main(){
    int n,m;
    cin>>n>>m;
    if(n>5000)return 0;
    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;
    }
    /*cout<<"dw"<<endl;
    rep(i,n)cout<<i<<":"<<ys[i]<<endl;
    cout<<"---"<<endl;
    rep(i,n)cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<" "<<d[i]<<endl;*/
    rep(i,m){
	ll ans=0;
	for(int j=a[i];j<b[i];j++){
	    ans+=(c[i]<=ys[j]&&ys[j]<d[i]);
	}
	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:37:6:
  rep(j,s[i].size()/2)swap(s[i][j],s[i][s[i].size()-1-j]);
      ~~~~~~~~~~~~~~~           
selling_rna.cpp:37: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:44:6:
  rep(j,q[i].size()/2)swap(q[i][j],q[i][q[i].size()-1-j]);
      ~~~~~~~~~~~~~~~           
selling_rna.cpp:44: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 11 ms 9768 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9724 KB Output is correct
5 Correct 11 ms 9720 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 11 ms 9720 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 22884 KB Output is correct
2 Correct 278 ms 22996 KB Output is correct
3 Correct 252 ms 23032 KB Output is correct
4 Correct 259 ms 23112 KB Output is correct
5 Correct 169 ms 18132 KB Output is correct
6 Correct 175 ms 18260 KB Output is correct
7 Correct 323 ms 24696 KB Output is correct
8 Correct 349 ms 25428 KB Output is correct
9 Correct 346 ms 25428 KB Output is correct
10 Correct 239 ms 20436 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 9720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9768 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9724 KB Output is correct
5 Correct 11 ms 9720 KB Output is correct
6 Correct 12 ms 9720 KB Output is correct
7 Correct 11 ms 9720 KB Output is correct
8 Correct 235 ms 22884 KB Output is correct
9 Correct 278 ms 22996 KB Output is correct
10 Correct 252 ms 23032 KB Output is correct
11 Correct 259 ms 23112 KB Output is correct
12 Correct 169 ms 18132 KB Output is correct
13 Correct 175 ms 18260 KB Output is correct
14 Correct 323 ms 24696 KB Output is correct
15 Correct 349 ms 25428 KB Output is correct
16 Correct 346 ms 25428 KB Output is correct
17 Correct 239 ms 20436 KB Output is correct
18 Incorrect 11 ms 9720 KB Output isn't correct
19 Halted 0 ms 0 KB -