Submission #222351

#	Time	Username	Problem	Language	Result	Execution time	Memory
222351		shenxy	Grudanje (COCI19_grudanje)	C++11	0 / 70	627 ms	499916 KiB

grudanje

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> ii;
struct seg {
	int s, e, m;
	ii v;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e, m = (s + e) / 2;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
			v = max(l -> v, r -> v);
		} else v = ii(0, s);
	}
	void update(int i, int dv) {
		if (s == e) {
			v.first = dv;
			return;
		} else if (i > m) r -> update(i, dv);
		else l -> update(i, dv);
		v = max(l -> v, r -> v);
	}
	ii query(int a, int b) {
		if (s == a && e == b) return v;
		if (a > m) return r -> query(a, b);
		if (b <= m) return l -> query(a, b);
		return max(l -> query(a, b), r -> query(a, b));
	}
} *root[26];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string S;
	cin >> S;
	int Q;
	cin >> Q;
	int a[Q], b[Q], p[S.size()], ans = 0;
	for (int i = 0; i < Q; ++i) cin >> a[i] >> b[i];
	for (int i = 0; i < S.size(); ++i) cin >> p[i];
	for (int i = 0; i < 26; ++i) root[i] = new seg(0, S.size() - 1);
	for (int i = 0; i < S.size(); ++i) root[S[i] - 'a'] -> update(i, p[i]);
	for (int i = 0; i < Q; ++i) {
		for (int j = 0; j < 26; ++j) {
			ii mx = root[j] -> query(a[i] - 1, b[i] - 1);
			root[j] -> update(mx.second, 0);
			ans = max(ans, (root[j] -> query(a[i] - 1, b[i] - 1)).first);
			root[j] -> update(mx.second, mx.first);
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); ++i) cin >> p[i];
                  ~~^~~~~~~~~~
grudanje.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); ++i) root[S[i] - 'a'] -> update(i, p[i]);
                  ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 7
• Subtask 5: 0 / 7
• Subtask 6: 0 / 7
• Subtask 7: 0 / 7
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7