Submission #864474

#	Time	Username	Problem	Language	Result	Execution time	Memory
864474		NeroZein	Zoltan (COCI16_zoltan)	C++17	140 / 140	278 ms	18364 KiB

zoltan

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 2e5 + 5;
const int md = (int) 1e9 + 7; 

int a[N], p2[N]; 
pair<int, int> seg[N * 2];
pair<int, int> lis[N], lds[N]; 

void add(int& x, int y) {
  x += y;
  if (x >= md) x -= md;
}

int mul(int x, int y) {
  return (int) ((long long) x * y % md); 
}

pair<int, int> comb(pair<int,int> x, pair<int,int> y) {
  if (x.first == y.first) {
    return {x.first, (x.second + y.second) % md};
  }
  return max(x, y); 
}

void upd(int nd, int l, int r, int p, pair<int, int> v) {
  if (l == r) {
    seg[nd] = v; 
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    upd(nd + 1, l, mid, p, v);
  } else {
    upd(rs, mid + 1, r, p, v); 
  }
  seg[nd] = comb(seg[nd + 1], seg[rs]); 
}

pair<int, int> qry(int nd, int l, int r, int s, int e) {
  if (l >= s && r <= e) {
    return seg[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    return qry(nd + 1, l, mid, s, e); 
  } else {
    if (mid < s) {
      return qry(rs, mid + 1, r, s, e); 
    } else {
      return comb(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e)); 
    }
  }
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  p2[0] = 1;
  for (int i = 1; i < N; ++i) {
    p2[i] = mul(p2[i - 1], 2); 
  }
  int n;
  cin >> n;
  map<int, int> mp; 
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    mp[a[i]];
  }
  int cnt = 0;
  for (auto& it : mp) {
    it.second = cnt++; 
  }
  for (int i = 0; i < n; ++i) {
    a[i] = mp[a[i]]; 
  }
  vector<int> id(n);
  iota(id.begin(), id.end(), 0);
  sort(id.begin(), id.end(), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] > a[j]; 
  });
  upd(0, 0, n, n, {0, 1}); 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lis[ind] = qry(0, 0, n, ind, n);
    lis[ind].first++; 
    upd(0, 0, n, ind, lis[ind]); 
  }
  for (int i = 0; i < N * 2; ++i) {
    seg[i] = {0, 0}; 
  }
  sort(id.begin(), id.end(), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j]; 
  });
  int mx = 1; 
  upd(0, 0, n, n, {0, 1}); 
  for (int i = 0; i < n; ++i) {
    int ind = id[i];
    lds[ind] = qry(0, 0, n, ind, n);
    lds[ind].first++;
    upd(0, 0, n, ind, lds[ind]); 
    mx = max(mx, lis[ind].first + lds[ind].first - 1); 
  }
  cnt = 0; 
  for (int i = 0; i < n; ++i) {
    if (lis[i].first + lds[i].first == mx + 1) {
      add(cnt, mul(p2[n - mx], mul(lds[i].second, lis[i].second)));
    }
  }
  cout << mx << ' ' << cnt << '\n'; 
  return 0;
}

• Subtask 1: 140 / 140