Submission #99742

#	Time	Username	Problem	Language	Result	Execution time	Memory
99742		wjoao	Zoltan (COCI16_zoltan)	C++11	140 / 140	598 ms	24084 KiB

zoltan

#include<bits/stdc++.h>
#define mod 1000000007
#define maxn 200010
#define par pair<int, int>
#define x first // Tamanho sequencia.
#define y second // Quantidade de formas diferentes.
#define int long long

using namespace std;

/*
  Problema: https://oj.uz/problem/view/COCI16_zoltan
  Solução:
  1) Para todo X, considerar apenas os elementos a direita (que serão colocados após ele).
  1.1) Considerar que os menores serão colocados a esquerda, e os maiores a direita.
  1.3) Calcular as duas soluções de X, ele sendo o menor de uma possível sequência ou o maior.

  2) Para todo X calcular como se ele fosse o meio, e combinar a subsequência com os elementos a esquerda que ele é maior, com a subsequência com os elementos da direita que ele é o menor.
*/


int add(int a, int b){
  int r = a+b;
  if( r > mod ) r -= mod;
  return r;
}

par join(par a, par b){
  if(a.x == b.x) return par(a.x, add(b.y,a.y));
  else return max(a,b);
}

struct BIT_PREFIX{
	par v[maxn];
	void update(int x, par val){
		for(; x < maxn; x += x&-x)
			v[x] = join(v[x], val);
	}
	par query(int x){
		if( x <= 0 ) return par(0,0);
		if( x >= maxn ) x = maxn-1;
		
		par sum;
		for(; x > 0; x -= x&-x)
			sum = join(v[x], sum);
		return sum;
	}
} bit_prefix;

struct BIT_SUFFIX{
	par v[maxn];
	void update(int x, par val){
		for(; x > 0; x -= x&-x)
			v[x] = join(v[x], val);
	}
	par query(int x){
		if( x <= 0 ) x = 1;
		if( x >= maxn ) par(0,0);
		
		par sum;
		for(; x < maxn; x += x&-x)
			sum = join(sum, v[x]);
		return sum;
	}
} bit_suffix;

int n, v[maxn], pot2[maxn];
map<int, int> compress;

main(){
  pot2[0] = 1;
  for(int i = 1; i < maxn; i++) pot2[i] = (pot2[i-1]*2)%mod;

  scanf("%lld", &n);
  for(int i = 0; i < n; i++)
    scanf(" %lld", &v[i]), compress[v[i]];
  // Comprimindo as coordenadas
  int id = 2;
  for(auto it = compress.begin(); it != compress.end(); it++, id++)
    it->second = id;
  
  for(int i = 0; i < n; i++)
    v[i] = compress[v[i]];

  // Calculando LIS pra crescentes e decrescentes
  par res;
  for(int i = n-1; i >= 0; i--){
    // Achar a melhor solução com um valor menor que o dele
    par crescente = bit_prefix.query(v[i]-1);
    // Se não existe solução, inicializar com uma forma possivel de tamanho 0
    if(crescente.x == 0) crescente = par(0, 1);
    // Achar a melhor solução com um valor maior que o dele
    par decrescente = bit_suffix.query(v[i]+1);
    // Se não existe solução, inicializar com uma forma possivel de tamanho 0
    if(decrescente.x == 0) decrescente = par(0, 1);

    // Calculando uma possível solução com o v[i] no centro.
    par sol_possivel = par(crescente.x + decrescente.x + 1, (crescente.y * decrescente.y)%mod);
    // Concatenando ou substituindo a melhor solução já encontrada.
    res = join(res, sol_possivel);

    // Atualizando a BIT
    crescente.x++;
    bit_prefix.update(v[i], crescente);

    decrescente.x++; 
    bit_suffix.update(v[i], decrescente);
  }

  res.y = (res.y * pot2[n-res.x]) % mod;

  printf("%lld %lld\n", res.x, res.y);
  return 0;
}

Compilation message (stderr)

zoltan.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
zoltan.cpp: In function 'int main()':
zoltan.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &n);
   ~~~~~^~~~~~~~~~~~
zoltan.cpp:76:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %lld", &v[i]), compress[v[i]];

• Subtask 1: 140 / 140