CSES - Datatähti 2020 loppu - Results
Submission details
Task:Riippuliito
Sender:Aaron Äärelä
Submission time:2020-02-09 14:00:31 +0200
Language:C++11
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int f(int)':
input/code.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tt[k].size(); i++){
                 ~~^~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < h.size(); i++){
                 ~~^~~~~~~~~~
input/code.cpp:62:21: error: expected ')' before ';' token
   d = max(d, f(h[i]);
                     ^

Code

#include <bits/stdc++.h>
using namespace std;
const int si = 1 << 17;
const int si2 = si / 2;
int t[si] = {};
vector<int> tt[si] = {};
int rakenna(int k){
	if(k >= si2) return t[k];
	t[k] = max(rakenna(2 * k), rakenna(2 * k + 1));
	return t[k];
}
int sum(int a, int b){
	a += si2;
	b += si2;
	int m = 0;
	while(a <= b){
		if(a % 2 == 1) m = max(m, t[a++]);
		if(b % 2 == 0) m = max(m, t[b--]);
		a /= 2;
		b /= 2;
	}
	return m;
}
int f(int k){
	int m = 0;
	for(int i = 0; i < tt[k].size(); i++){
		m = max(m, f(tt[k][i]));
	}
	return m + 1;
}
int main(){
	int n;
	cin >>n;
	t[0] = 0;
	vector<int> h;
	int m = 0;
	for(int i = 0; i < n; i++){
		cin >> t[i + si2];
		if(t[i + si2] > m) {
			h.clear();
			m = t[i + si2];
			h.push_back(i);
		}
		else if(t[i + si2] == m) h.push_back(i);
	}
	rakenna(1);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			if(i == j) continue;
			if(i > j){
				int s = sum(j, i - 1);
				if(s < t[i + si2]) tt[i].push_back(j);
			}
			else {
				int s = sum(i + 1, j);
				if(s < t[i + si2]) tt[i].push_back(j);
			}
		}
	}
	int d = 0;
	for(int i = 0; i < h.size(); i++){
		d = max(d, f(h[i]);
	}
	cout << d << '\n';
	return 0;
}