CSES - Datatähti 2019 alku - Results
Submission details
Task:Taulukko
Sender:Ilmari2000
Submission time:2018-10-07 23:32:54 +0300
Language:C++
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:43:6: error: expected '{' before ':' token
   try:
      ^
input/code.cpp:43:6: error: expected 'catch' before ':' token
input/code.cpp:43:6: error: expected '(' before ':' token
input/code.cpp:43:6: error: expected type-specifier before ':' token
input/code.cpp:43:6: error: expected ')' before ':' token
input/code.cpp:43:6: error: expected '{' before ':' token
input/code.cpp:43:6: error: expected primary-expression before ':' token
input/code.cpp:46:3: error: expected primary-expression before 'catch'
   catch:
   ^~~~~
input/code.cpp:37:7: warning: unused variable 'si' [-Wunused-variable]
   int si = i;
       ^~
input/code.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ranges.size(); i++)
                 ~~^~~~~~~~~~~~~~~
input/code.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; i + j < rang...

Code

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

long long int tri(long long int n)
{
	return (n * (n + 1)) / 2;
}

int main()
{
	int n, k;
	cin >> n >> k;

	int *a = new int[n];
	for(int i = 0; i < n; i++)
		cin >> a[i];

	map<int, int> cn;
	vector<map<int, int>> next;
	next.resize(n);

	for(int i = n - 1; i >= 0; i--)
	{
		next[i] = cn;
		cn[a[i]] = i + 1;
	}

	vector<pair<int, int>> ranges, overlaps;
	vector<int> ols;

	for(int i = 0; i < n; i++)
	{
		int si = i;
		if(i) for(; i < n && a[i-1] == a[i]; i++);
		
		if(i == n)
			break;

		try:
			if(si && next[i][a[i-1]] && next[i][a[i-1]] - 1 <= ranges.back().second)
				continue;
		catch:
			;
		
		set<int> nums;
		int u = 0;

		int j = i;
		for(; j < n; j++)
		{
			if(!nums.count(a[j]))
			{
				nums.insert(a[j]);
				u++;
				if(u > k)
					break;
			}
		}

		if(ranges.empty() || ranges.back().second < j-1)
			ranges.push_back(make_pair(i, j-1));	
	}

	for(int i = 0; i < ranges.size(); i++)
	{
		//cout << "(" << ranges[i].first << ", " << ranges[i].second << "): ";
		for(int j = 1; i + j < ranges.size(); j++)
		{
			if(ranges[i].second < ranges[i+j].first)
				break;

			//cout << "(" << ranges[i+j].first << ", " << ranges[i+j].second << "), ";
			//overlaps.push_back(make_pair(ranges[i+j].first, ranges[i].second));
			ols.push_back(ranges[i].second - ranges[i+j].first + 1);
		}
		//cout << endl;
	}

	/*for(pair<int, int> p : ranges)
		cout << p.first << ", " << p.second << endl;

	cout << endl;
	for(int i = 0; i < ols.size(); i++)
		cout << overlaps[i].first << ", " << overlaps[i].second << ", " << ols[i] << endl;*/

	long long int ret = 0;

	for(pair<int, int> p : ranges)
		ret += tri(p.second - p.first + 1);

	for(int i : ols)
		ret -= tri(i);

	cout << ret << endl;
}