Submission #767334

#	Time	Username	Problem	Language	Result	Execution time	Memory
767334		jmyszka2007	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	281 ms	283584 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pi pair<int, int>
#define pb push_back
constexpr int LIM = 4e6;
constexpr int base = (1 << 22);
int gpref[LIM + 10][26];
int gsuf[LIM + 10][26];
int prepref[LIM + 10];
int sizpref[LIM + 10];
int presuf[LIM + 10];
int sizsuf[LIM + 10];
int res[LIM + 10];
int tri[2 * base];
void upd(int v) {
	v += base;
	while(v > 0) {
		tri[v]++;
		v /= 2;
	}
}
int que(int l, int r) {
	l += base;
	r += base;
	int ans = 0;
	while(l <= r) {
		if(l & 1) {
			ans += tri[l];
		}
		if(!(r & 1)) {
			ans += tri[r];
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
int aktpre = 1;
void dfspref(int v) {
	prepref[v] = aktpre++;
	sizpref[v] = 1;
	for(int i = 0; i < 26; i++) {
		if(gpref[v][i]) {
			dfspref(gpref[v][i]);
			sizpref[v] += sizpref[gpref[v][i]];
		}
	}
}
void dfssuf(int v) {
	presuf[v] = aktpre++;
	sizsuf[v] = 1;
	for(int i = 0; i < 26; i++) {
		if(gsuf[v][i]) {
			dfssuf(gsuf[v][i]);
			sizsuf[v] += sizsuf[gsuf[v][i]];
		}
	}
}
int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	int n, t;
	cin >> n >> t;
	int cntpref = 2;
	int cntsuf = 2;
	vector<pair<pi, pi> >zap;
	for(int i = 1; i <= n; i++) {
		string a;
		cin >> a;
		pi pkt;
		int akt = 1;
		for(auto x : a) {
			if(!gpref[akt][x - 'A']) {
				gpref[akt][x - 'A'] = cntpref++;
			}
			akt = gpref[akt][x - 'A'];
		}
		pkt.st = akt;
		reverse(a.begin(), a.end());
		akt = 1;
		for(auto x : a) {
			if(!gsuf[akt][x - 'A']) {
				gsuf[akt][x - 'A'] = cntsuf++;
			}
			akt = gsuf[akt][x - 'A'];
		}
		pkt.nd = akt;
		zap.pb({pkt, {0, 0}});
	}
	for(int i = 1; i <= t; i++) {
		string a, b;
		cin >> a >> b;
		reverse(b.begin(), b.end());
		pi pkt;
		int akt = 1;
		for(auto x : a) {
			if(!gpref[akt][x - 'A']) {
				gpref[akt][x - 'A'] = cntpref++;
			}
			akt = gpref[akt][x - 'A'];
		}
		pkt.st = akt;
		akt = 1;
		for(auto x : b) {
			if(!gsuf[akt][x - 'A']) {
				gsuf[akt][x - 'A'] = cntsuf++;
			}
			akt = gsuf[akt][x - 'A'];
		}
		pkt.nd = akt;
		zap.pb({pkt, {0, i}});
	}
	dfspref(1);
	aktpre = 1;
	dfssuf(1);
	vector<pair<pi, pi> >nzap;
	/*for(int i = 1; i < cntpref; i++) {
		cout << i << ' ' << prepref[i] << ' ' << sizpref[i] << ":\n";
		for(int j = 0; j < 26; j++) {
			if(gpref[i][j]) {
				cout << gpref[i][j] << ' ';
			}
		}
		cout << '\n';
	}*/
	for(int i = 0; i < zap.size(); i++) {
		int a = prepref[zap[i].st.st];
		int b = presuf[zap[i].st.nd];
		//cout << a << ' ' << b << '\n';
		if(!zap[i].nd.nd) {
			nzap.pb({{a, 0}, {0, b}});
		}
		else {
			nzap.pb({{a - 1, b}, {b + sizsuf[zap[i].st.nd] - 1, -zap[i].nd.nd}});
			nzap.pb({{a + sizpref[zap[i].st.st] - 1, b}, {b + sizsuf[zap[i].st.nd] - 1, zap[i].nd.nd}});
		}
	}
	sort(nzap.begin(), nzap.end());
	for(auto x : nzap) {
		//cout << x.st.st << ' ' << x.st.nd << ' ' << x.nd.st << ' ' << x.nd.nd << '\n';
		if(!x.st.nd) {
			upd(x.nd.nd);
		}
		else {
			if(x.nd.nd < 0) {
				res[-x.nd.nd] -= que(x.st.nd, x.nd.st);
			}
			else {
				res[x.nd.nd] += que(x.st.nd, x.nd.st);
			}
		}
	}
	for(int i = 1; i <= t; i++) {
		cout << res[i] << '\n';
	}
}

Compilation message (stderr)

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for(int i = 0; i < zap.size(); i++) {
      |                 ~~^~~~~~~~~~~~

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