Submission #496019

#	Time	Username	Problem	Language	Result	Execution time	Memory
496019		Nimbostratus	Grudanje (COCI19_grudanje)	C++17	70 / 70	174 ms	15532 KiB

grudanje

#include "bits/stdc++.h"
#define endl '\n'
#define fi first
#define se second
constexpr int maxn = 1e5 + 5;
constexpr int inf = 2e9;
constexpr int mod = 1e9 + 7;
using namespace std;
using lint = long long;
using pii = pair<int, int>;

int n;
int m;
string s;
int stime[maxn];
int cnt[maxn][26];
vector<int> qry[maxn];
queue<pii> q;

bool check(int k) {
	while(!q.empty())
		q.pop();
	for(int i = 1; i <= n + 1; i++) {
		while(!q.empty()) {
			int l = q.front().fi, r = q.front().se;
			if(r > i - 1)
				break;
			q.pop();
			for(int j = 0; j < 26; j++)
				if(cnt[r][j] - cnt[l - 1][j] >= 2)
					return false;
		}
		for(int j : qry[i])
			q.push({i, j});
		for(int j = 0; j < 26; j++)
			cnt[i][j] = cnt[i - 1][j];
		if(stime[i] > k)
			cnt[i][s[i] - 'a']++;
	}
	return true;
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> s;
	n = s.size();
	s = ' ' + s;
	cin >> m;
	for(int x, y; m--;) {
		cin >> x >> y;
		qry[x].push_back(y);
	}
	for(int i = 1, x; i <= n; i++) {
		cin >> x;
		stime[x] = i;
	}
	int lo = 0, hi = n, mid;
	while(lo < hi - 1) {
		mid = (lo + hi) >> 1;
		if(check(mid))
			hi = mid;
		else
			lo = mid + 1;
	}
	cout << (check(lo) ? lo : hi) << endl;
}

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