제출 #159954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
159954		iefnah06	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	415 ms	181340 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;

int toInt(char c) {
	static const char alpha[] = "AGCU";
	int res = 0;
	for (; alpha[res] != c; res++);
	return res;
}

const int MAXN = 1.1e5;
const int MAXQ = 1.1e5;
int N, Q;

const int MAXL = 1.1e5;
char S[MAXL];

struct trie {
	trie* ch[4];
	int st, en;
};
trie* ROOTS[2];
trie* tnull;
void initTrie() {
	for (int flip = 0; flip < 2; flip++) {
		ROOTS[flip] = new trie();
	}
	tnull = new trie();
}

trie* insert(int len, trie* r) {
	for (int i = 0; i < len; i++) {
		int c = S[i];
		if (r->ch[c] == NULL) {
			r->ch[c] = new trie();
		}
		r = r->ch[c];
	}
	return r;
}

trie* query(int len, trie* r) {
	for (int i = 0; i < len; i++) {
		int c = S[i];
		if (r->ch[c] == NULL) {
			return tnull;
		}
		r = r->ch[c];
	}
	return r;
}

trie* locs[MAXN][2];

void dfs(trie* r, int& ind) {
	if (r == NULL) return;
	r->st = ind++;
	for (int c = 0; c < 4; c++) {
		dfs(r->ch[c], ind);
	}
	r->en = ind;
}

const int MAXV = 2.1e6;
int coords[MAXN][2];
int V[2] = {0, 0};
vector<int> pts[MAXV];

struct seg {
	seg* ch[2];
	int val;
};
seg* null;
void initSeg() {
	null = new seg();
	null->ch[0] = null->ch[1] = null;
	null->val = 0;
}

seg* segs[MAXV];

seg* update(int p, seg* r, int x = 0, int y = V[1]) {
	seg* n = new seg(*r);
	n->val++;
	if (y - x > 1) {
		int z = (x + y) / 2;
		if (p < z) {
			n->ch[0] = update(p, r->ch[0], x, z);
		} else {
			n->ch[1] = update(p, r->ch[1], z, y);
		}
	}
	return n;
}

int query(int l, int r, seg* n, int x = 0, int y = V[1]) {
	int res = 0;
	if (n != null) {
		if (l <= x && y <= r) {
			res = n->val;
		} else {
			int z = (x + y) / 2;
			if (l < z) {
				res += query(l, r, n->ch[0], x, z);
			}
			if (z < r) {
				res += query(l, r, n->ch[1], z, y);
			}
		}
	}
	return res;
}

bool inRange(int a, int mi, int ma) {
	return mi <= a && a < ma;
}

int querySlow(int xlo, int xhi, int ylo, int yhi) {
	int res = 0;
	for (int i = 0; i < N; i++) {
		res += inRange(coords[i][0], xlo, xhi) && inRange(coords[i][1], ylo, yhi);
	}
	return res;
}

int query(int xlo, int xhi, int ylo, int yhi) {
	assert(xlo <= xhi && ylo <= yhi);
//	return querySlow(xlo, xhi, ylo, yhi);
	return query(ylo, yhi, segs[xhi]) - query(ylo, yhi, segs[xlo]);
}

int main() {
	scanf("%d %d", &N, &Q);
	initTrie();
	for (int i = 0; i < N; i++) {
		scanf("%s", S);
		int len = int(strlen(S));
		for (int j = 0; j < len; j++) {
			S[j] = toInt(S[j]);
		}
		for (int flip = 0; flip < 2; flip++) {
			locs[i][flip] = insert(len, ROOTS[flip]);
			reverse(S, S + len);
		}
	}

	for (int flip = 0; flip < 2; flip++) {
		int ind = 0;
		dfs(ROOTS[flip], ind);
	}

	for (int i = 0; i < N; i++) {
		for (int flip = 0; flip < 2; flip++) {
			coords[i][flip] = locs[i][flip]->st;
			V[flip] = max(V[flip], coords[i][flip] + 1);
		}
		pts[coords[i][0]].push_back(coords[i][1]);
	}

	initSeg();
	segs[0] = null;
	for (int x = 0; x < V[0]; x++) {
		segs[x+1] = segs[x];
		for (size_t i = 0; i < pts[x].size(); i++) {
			int y = pts[x][i];
			assert(y < V[1]);
			segs[x+1] = update(y, segs[x+1]);
		}
	}

	for (int q = 0; q < Q; q++) {
		trie* Slocs[2];
		for (int flip = 0; flip < 2; flip++) {
			scanf("%s", S);
			int len = int(strlen(S));
			for (int j = 0; j < len; j++) {
				S[j] = toInt(S[j]);
			}
			if (flip) {
				reverse(S, S + len);
			}
			Slocs[flip] = query(len, ROOTS[flip]);
		}

		int ans = query(Slocs[0]->st, Slocs[0]->en, Slocs[1]->st, Slocs[1]->en); 
		printf("%d\n", ans);
	}

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~
selling_rna.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S);
   ~~~~~^~~~~~~~~
selling_rna.cpp:174:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%s", S);
    ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40