oj.uz

Submission #494125

# Submission time Handle Problem Language Result Execution time Memory
494125 2021-12-14T12:17:46 Z stefantaga Zoltan (COCI16_zoltan) C++14
140 / 140
 131 ms 11216 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define TRACE(x) cout << #x << " = " << x << endl;

typedef long long int llint;

typedef pair<int, int> par;

#define X first
#define Y second

const int MAXN = 500010, MOD = 1000000007;

inline int add(int a, int b)
{
  int ret = a + b;
  if(ret >= MOD) ret -= MOD;
  return ret;
}

inline int mul(int a, int b)
{
  llint ret = (llint)a * b;
  if(ret >= MOD) ret %= MOD;
  return ret;
}

int n;
int niz[MAXN], dva[MAXN];

par A[MAXN], B[MAXN];
par FWT_gore[MAXN], FWT_dolje[MAXN];

par rj;

par spoji(par a, par b)
{
 if(b.X > a.X)
 {
   a.X = b.X;
   a.Y = b.Y;
 } 
 else if(b.X == a.X)
   a.Y = add(a.Y, b.Y);
 return a;
}

void ubaci_gore(int x, par v)
{
  x += 5;
  for(; x < MAXN; x += x & -x)
    FWT_gore[x] = spoji(FWT_gore[x], v);
}

par upit_gore(int x)
{
  x += 5;
  par ret(0, 0);
  for(; x > 0; x -= x & -x)
    ret = spoji(ret, FWT_gore[x]);
  return ret;
}

void ubaci_dolje(int x, par v)
{
  x += 5;
  for(; x > 0; x -= x & -x)
    FWT_dolje[x] = spoji(FWT_dolje[x], v);
}

par upit_dolje(int x)
{
  x += 5;
  par ret(0, 0);
  for(; x < MAXN; x += x & -x)
    ret = spoji(ret, FWT_dolje[x]);
  return ret;
}

void sazmi()
{
  vector<int> v;
  for(int i = 0; i < n; i++)
    v.push_back(niz[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for(int i = 0; i < n; i++)
    niz[i] = lower_bound(v.begin(), v.end(), niz[i]) - v.begin();
}

void sredi_gore()
{
  for(int i = n - 1; i >= 0; i--)
  {
    par p = upit_gore(niz[i] - 1);
    if(p.X == 0)
    {
      A[i] = par(0, 1);
      ubaci_gore(niz[i], par(1, 1));
    }
    else 
    {
      A[i] = p;
      p.X++;
      ubaci_gore(niz[i], p);
    }
  }
}

void sredi_dolje()
{
  for(int i = n - 1; i >= 0; i--)
  {
    par p = upit_dolje(niz[i] + 1);
    if(p.X == 0)
    {
      B[i] = par(0, 1);
      ubaci_dolje(niz[i], par(1, 1));
    }
    else
    {
      B[i] = p;
      p.X++;
      ubaci_dolje(niz[i], p);
    }
  }
}

void postavi()
{
  dva[0] = 1;
  for(int i = 1; i < MAXN; i++)
    dva[i] = mul(dva[i - 1], 2);
}

void glavno()
{
  for(int i = 0; i < n; i++)
    rj = spoji(rj, par(A[i].X + 1 + B[i].X, mul(A[i].Y, B[i].Y)));
  rj.Y = mul(rj.Y, dva[n - rj.X]);
}

int main()
{
  postavi();
  scanf("%d", &n);
  for(int i = 0; i < n; i++)
    scanf("%d", &niz[i]);
  sazmi();
  sredi_gore();
  sredi_dolje();
  glavno();
  printf("%d %d\n", rj.X, rj.Y);
  return 0;
}

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
zoltan.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |     scanf("%d", &niz[i]);
      |     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2272 KB Output is correct
2 Correct 6 ms 2268 KB Output is correct
3 Correct 6 ms 2256 KB Output is correct
4 Correct 4 ms 2256 KB Output is correct
5 Correct 5 ms 2256 KB Output is correct
6 Correct 4 ms 2256 KB Output is correct
7 Correct 5 ms 2256 KB Output is correct
8 Correct 5 ms 2384 KB Output is correct
9 Correct 6 ms 2384 KB Output is correct
10 Correct 5 ms 2256 KB Output is correct
11 Correct 66 ms 9192 KB Output is correct
12 Correct 85 ms 8272 KB Output is correct
13 Correct 55 ms 7864 KB Output is correct
14 Correct 80 ms 8572 KB Output is correct
15 Correct 105 ms 10072 KB Output is correct
16 Correct 131 ms 11216 KB Output is correct
17 Correct 86 ms 10108 KB Output is correct
18 Correct 93 ms 10308 KB Output is correct
19 Correct 88 ms 10120 KB Output is correct
20 Correct 98 ms 10196 KB Output is correct