Submission #496012

#	Time	Username	Problem	Language	Result	Execution time	Memory
496012		Nimbostratus	Grudanje (COCI19_grudanje)	C++17	0 / 70	353 ms	248356 KiB

grudanje

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

struct item {
	int l, r;
	vector<int> prev;
};

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

bool check(int k) {
	vector<int> cnt(26, 0);
	for(int i = 1; i <= n + 1; i++) {
		while(!q.empty() && q.front().r == i - 1) {
			auto& prev = q.front().prev;
			for(int j = 0; j < 26; j++)
				if(cnt[j] - prev[j] >= 2)
					return false;
			q.pop();
		}
		for(int j : qry[i])
			q.push({i, j, cnt});
		if(stime[i] > k)
			cnt[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 l = 0, r = n, mid;
	while(l < r - 1) {
		mid = (l + r) >> 1;
		if(check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	cout << (check(l) ? l : r) << endl;
}

• 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