oj.uz

Submission #99742

# Submission time Handle Problem Language Result Execution time Memory
99742 2019-03-06T14:45:03 Z wjoao Zoltan (COCI16_zoltan) C++11
140 / 140
 598 ms 24084 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1920 KB Output is correct
2 Correct 5 ms 1920 KB Output is correct
3 Correct 5 ms 1920 KB Output is correct
4 Correct 5 ms 1920 KB Output is correct
5 Correct 5 ms 1920 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 5 ms 2048 KB Output is correct
8 Correct 5 ms 2048 KB Output is correct
9 Correct 5 ms 2048 KB Output is correct
10 Correct 7 ms 2048 KB Output is correct
11 Correct 285 ms 19300 KB Output is correct
12 Correct 241 ms 16880 KB Output is correct
13 Correct 210 ms 16016 KB Output is correct
14 Correct 411 ms 17288 KB Output is correct
15 Correct 544 ms 21280 KB Output is correct
16 Correct 598 ms 24084 KB Output is correct
17 Correct 341 ms 20600 KB Output is correct
18 Correct 280 ms 20600 KB Output is correct
19 Correct 307 ms 20632 KB Output is correct
20 Correct 306 ms 20476 KB Output is correct