oj.uz

Submission #95920

# Submission time Handle Problem Language Result Execution time Memory
95920 2019-02-04T09:55:44 Z Retro3014 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 675 ms 72908 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>

using namespace std;
typedef long long ll;
#define MAX_M 100000

int N, M;
vector<string> S, P, Q;
string str;
struct ST{
	ST (string s, int idx, bool b1, bool b2) : s(s), idx(idx), b1(b1), b2(b2) {}
	string s;
	int idx;
	bool b1, b2;
	bool operator <(const ST &a)const{
		return s<a.s;
	}
};
vector<ST> v1, v2;
struct PT{
	PT (int x, int y) : x(x), y(y) {}
	int x, y;
};
vector<PT> vS, vP[2];

struct SEG{
	SEG (int sum, int l, int r) : sum(sum), l(l), r(r) {}
	int sum;
	int l, r;
};
vector<SEG> seg;

void update(int idx, int s, int e, int k){
	seg[idx].sum++;
	if(s==e)	return;
	if(k<=(s+e)/2){
		if(seg[idx].l==-1){
			seg[idx].l = seg.size();
			seg.push_back({0, -1, -1});
		}
		update(seg[idx].l, s, (s+e)/2, k);
	}else{
		if(seg[idx].r==-1){
			seg[idx].r = seg.size();
			seg.push_back({0, -1, -1});
		}
		update(seg[idx].r, (s+e)/2+1, e, k);
	}
}

int sum(int idx, int s, int e, int x, int y){
	if(idx==-1)	return 0;
	if(x<=s && e<=y)	return seg[idx].sum;
	if(x>e || y<s)	return 0;
	return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}

struct S2{
	S2 (int idx, int type, int x1, int x2, int y) : idx(idx), type(type), x1(x1), x2(x2), y(y) {}
	int idx, type;
	int x1, x2, y;
	bool operator <(const S2 &a)const{
		if(y==a.y){
			return type<a.type;
		}
		return y<a.y;
	}
};

vector<S2> query;
int ans[MAX_M+1];

int main(){
	seg.push_back({0, -1, -1});
	scanf("%d%d", &N, &M);
	for(int i=0; i<N; i++){
		vS.push_back({0, 0});
		cin>>str;	S.push_back(str);
		//cout<<str<<endl;
		v1.push_back({S[i], i, 1, 0});
		for(int j=0; j<S[i].size(); j++){
			str[j] = S[i][S[i].size()-j-1];
		}
		//cout<<str<<endl;
		v2.push_back({str, i, 1, 0});
	}
	for(int i=0; i<M; i++){
		vP[0].push_back({0, 0});
		vP[1].push_back({0, 0});
		cin>>str; P.push_back(str);
		//cout<<str<<endl;
		v1.push_back({P[i], i, 0, 0});
		str[str.size()-1]++;
		//cout<<str<<endl;
		v1.push_back({str, i, 0, 1});
		cin>>str;
		Q.push_back(str);
		for(int j=0; j<Q[i].size(); j++){
			str[j] = Q[i][Q[i].size()-1-j];
		}
		Q[i] = str;
		//cout<<str<<endl;
		v2.push_back({Q[i], i, 0, 0});
		str[str.size()-1]++;
		//cout<<str<<endl;
		v2.push_back({str, i, 0, 1});
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	int index = 0;
	for(int i=0; i<v1.size(); i++){
		//cout<<v1[i].s<<' '<<v1[i].idx<<endl;
		if(i!=0 && v1[i].s!=v1[i-1].s)	index++;
		if(v1[i].b1){
			vS[v1[i].idx].x = index;
		}else{
			if(v1[i].b2){
				vP[1][v1[i].idx].x = index;
			}else{
				vP[0][v1[i].idx].x = index;
			}
		}
	}//cout<<endl;
	index = 0;
	for(int i=0; i<v2.size(); i++){
		//cout<<v2[i].s<<' '<<v2[i].idx<<' '<<endl;
		if(i!=0 && v2[i].s!=v2[i-1].s)	index++;
		if(v2[i].b1){
			vS[v2[i].idx].y = index;
		}else{
			if(v2[i].b2){
				vP[1][v2[i].idx].y = index;
			}else{
				vP[0][v2[i].idx].y = index-1;
			}
		}
	}
	for(int i=0; i<vS.size(); i++){
		query.push_back({i, 0, vS[i].x, 0, vS[i].y});
	}
	for(int i=0; i<vP[0].size(); i++){
		query.push_back({i, 1, vP[0][i].x, vP[1][i].x, vP[0][i].y});
		query.push_back({i, 2, vP[0][i].x, vP[1][i].x, vP[1][i].y});
	}
	sort(query.begin(), query.end());
	for(int i=0; i<query.size(); i++){
		S2 now = query[i];
		if(now.type==0){
			//cout<<now.idx<<endl;
			update(0, 0, v1.size(), now.x1);
		}else if(now.type==1){
			//cout<<now.idx<<' '<<-1<<endl;
			ans[now.idx]-=sum(0, 0, v1.size(), now.x1, now.x2);
		}else{
			//cout<<now.idx<<' '<<1<<endl;
			ans[now.idx]+=sum(0, 0, v1.size(), now.x1, now.x2);
		}
	}
	for(int i=0; i<M; i++){
		printf("%d\n", ans[i]);
	}
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:85:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<S[i].size(); j++){
                ~^~~~~~~~~~~~
selling_rna.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<Q[i].size(); j++){
                ~^~~~~~~~~~~~
selling_rna.cpp:115:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v1.size(); i++){
               ~^~~~~~~~~~
selling_rna.cpp:129:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
selling_rna.cpp:142:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vS.size(); i++){
               ~^~~~~~~~~~
selling_rna.cpp:145:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vP[0].size(); i++){
               ~^~~~~~~~~~~~~
selling_rna.cpp:150:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
selling_rna.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 17424 KB Output is correct
2 Correct 155 ms 19048 KB Output is correct
3 Correct 152 ms 18568 KB Output is correct
4 Correct 160 ms 18988 KB Output is correct
5 Correct 113 ms 13616 KB Output is correct
6 Correct 115 ms 13768 KB Output is correct
7 Correct 229 ms 24376 KB Output is correct
8 Correct 234 ms 27136 KB Output is correct
9 Correct 229 ms 27128 KB Output is correct
10 Correct 136 ms 17368 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 27652 KB Output is correct
2 Correct 111 ms 16112 KB Output is correct
3 Correct 141 ms 20812 KB Output is correct
4 Correct 120 ms 18132 KB Output is correct
5 Correct 110 ms 15996 KB Output is correct
6 Correct 142 ms 20852 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 137 ms 17424 KB Output is correct
9 Correct 155 ms 19048 KB Output is correct
10 Correct 152 ms 18568 KB Output is correct
11 Correct 160 ms 18988 KB Output is correct
12 Correct 113 ms 13616 KB Output is correct
13 Correct 115 ms 13768 KB Output is correct
14 Correct 229 ms 24376 KB Output is correct
15 Correct 234 ms 27136 KB Output is correct
16 Correct 229 ms 27128 KB Output is correct
17 Correct 136 ms 17368 KB Output is correct
18 Correct 157 ms 27652 KB Output is correct
19 Correct 111 ms 16112 KB Output is correct
20 Correct 141 ms 20812 KB Output is correct
21 Correct 120 ms 18132 KB Output is correct
22 Correct 110 ms 15996 KB Output is correct
23 Correct 142 ms 20852 KB Output is correct
24 Correct 225 ms 25692 KB Output is correct
25 Correct 337 ms 36596 KB Output is correct
26 Correct 180 ms 21844 KB Output is correct
27 Correct 222 ms 25800 KB Output is correct
28 Correct 675 ms 72908 KB Output is correct
29 Correct 562 ms 56968 KB Output is correct