Submission #254469

#	Time	Username	Problem	Language	Result	Execution time	Memory
254469		MrRobot_28	Grudanje (COCI19_grudanje)	C++17	70 / 70	148 ms	4216 KiB

grudanje

#include <bits/stdc++.h>
                  
using namespace std;
vector <int> tree;
vector <int> upd;
void push(int v, int l, int r)
{
	tree[v * 2] += upd[v];
	tree[v * 2 + 1] += upd[v];
	upd[v * 2] += upd[v];
	upd[v * 2 + 1] += upd[v];
	upd[v] =  0;
}
void update(int v, int l, int r, int al, int ar, int a)
{
	if(l >= al && r <= ar)
	{
		tree[v] += a;
		upd[v] += a;
	}
	else if(l <= ar && r >= al)
	{
		push(v, l, r);
		update(v * 2, l, (r + l) / 2, al, ar, a);
		update(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, a);
		tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
	}
}
signed main(){
//	ios_base::sync_with_stdio(false);
//	cin.tie(NULL);
//	cout.tie(NULL);
	string s;
	cin >> s;
	int n = s.size();
	int q;
	cin >> q;
	vector <pair <int, int> > queries(q);
	set <pair <int, int> > s1;
	for(int i = 0; i < q; i++)
	{
		cin >> queries[i].first >> queries[i].second;
		queries[i].first--;
		queries[i].second--;
	}
	sort(queries.begin(), queries.end());
	for(int i = 0; i < q; i++)
	{
		int j = i;
		while(j < q && queries[j].first == queries[i].first)
		{
			j++;
		}
		i = j - 1;
		if(s1.size()== 0 || s1.rbegin() -> first < queries[i].second)
		{
			s1.insert({queries[i].second, queries[i].first});
		}
	}
	queries.clear();
	set <pair <int, int> > :: iterator it;
	for(it = s1.begin(); it != s1.end(); it++)
	{
		queries.push_back({it -> second, it -> first});
	}
	q = queries.size();
	tree.resize(4 * q);
	upd.resize(4 * q);
	vector <vector <int> > p(26);
	vector <int> index1(n);
	for(int i = 0; i < n; i++)
	{
		int ind;
		cin >> ind;
		ind--;
		index1[ind] = i + 1;
		p[s[ind] - 'a'].push_back(ind);
	}
	vector <int> index(26);
	for(int c = 0; c < 26; c++)
	{
		for(int i = 0; i < 4 * q; i++){
			tree[i] = upd[i] = 0;
		}
		for(int i = 0; i < p[c].size(); i++)
		{
			int ind = p[c][i];
			int l = -1, r = queries.size();
			while(r - l > 1){
				int midd = (r + l) / 2;
				if(queries[midd].second < ind)
				{
					l = midd;
				}
				else
				{
					r = midd;
				}
			}
			int l1 = -1, r1 = queries.size();
			while(r1 - l1 > 1)
			{
				int midd = (r1 + l1) / 2;
				if(queries[midd].first > ind)
				{
					r1 = midd;
				}
				else
				{
					l1 = midd;
				}
			}
			if(l1 != -1 && r != queries.size() && queries[r].first <= ind && queries[r].second >= ind)
			{
				update(1, 0, q - 1, r, l1, 1);
			}
		}
		for(int i = 0; i <= p[c].size(); i++)
		{
			if(tree[1] <= 1)
			{
				if(i == 0)
				{
					index[c] = 0;
				}
				else
				{
					index[c] = index1[p[c][i - 1]];
				}
				break;
			}
			int ind = p[c][i];
			int l = -1, r = queries.size();
			while(r - l > 1){
				int midd = (r + l) / 2;
				if(queries[midd].second < ind)
				{
					l = midd;
				}
				else
				{
					r = midd;
				}
			}
			int l1 = -1, r1 = queries.size();
			while(r1 - l1 > 1)
			{
				int midd = (r1 + l1) / 2;
				if(queries[midd].first > ind)
				{
					r1 = midd;
				}
				else
				{
					l1 = midd;
				}
			}
			if(l1 != -1 && r != queries.size() && queries[r].first <= ind && queries[r].second >= ind)
			{
				update(1, 0, q - 1, r, l1, -1);
			}
		}
	}
	int ans = 0;
	for(int c = 0; c < 26; c++)
	{
		ans = max(ans, index[c]);
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

grudanje.cpp: In function 'int main()':
grudanje.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < p[c].size(); i++)
                  ~~^~~~~~~~~~~~~
grudanje.cpp:113:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(l1 != -1 && r != queries.size() && queries[r].first <= ind && queries[r].second >= ind)
                   ~~^~~~~~~~~~~~~~~~~
grudanje.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i <= p[c].size(); i++)
                  ~~^~~~~~~~~~~~~~
grudanje.cpp:158:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(l1 != -1 && r != queries.size() && queries[r].first <= ind && queries[r].second >= ind)
                   ~~^~~~~~~~~~~~~~~~~

• 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