Submission #198159

#	Time	Username	Problem	Language	Result	Execution time	Memory
198159		mkisic	Zoltan (COCI16_zoltan)	C++14	140 / 140	272 ms	11020 KiB

zoltan

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

typedef long long ll;
typedef double lf;
typedef long double Lf;
typedef pair <int,int> pii;
typedef pair <ll, ll> pll;

#define TRACE(x) cerr << #x << "  " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define _ << " " <<

#define fi first
#define sec second
#define mp make_pair
#define pb push_back

const int MAXN = 200100;
const int offset = (1 << 18);
const int MOD = 1e9 + 7;

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

int mul(int a, int b) {
  return (ll)a * b % MOD;
}

struct tournament {
  pii p[offset * 2];

  tournament() {
    REP(i, offset * 2) p[i] = {0, 0};
  }

  pii merge(pii a, pii b) {
    if (a.fi > b.fi) return a;
    if (b.fi > a.fi) return b;
    return {a.fi, add(a.sec, b.sec)};
  }

  void update(int a, pii b) {
    a += offset;
    p[a] = merge(p[a], b);
    a /= 2;
    while (a) {
      p[a] = merge(p[a * 2], p[a * 2 + 1]);
      a /= 2;
    }
  }

  pii get(int cvor, int l, int r, int a, int b) {
    if (l > b || r < a || l > r) return {0, 0};
    if (l >= a && r <= b) return p[cvor];

    int mid = (l + r) / 2;
    pii x = get(cvor * 2, l, mid, a, b);
    pii y = get(cvor * 2 + 1, mid + 1, r, a, b);
    return merge(x, y);
  }

  void clear() {
    REP(i, offset * 2) p[i] = {0, 0};
  }
};

tournament T;

int n;

vector <int> saz;
vector <pii> pt, pt1;

int pot[MAXN];
pii dp[2][MAXN];

int main() {
  pot[0] = 1;
  FOR(i, 1, MAXN) pot[i] = mul(2, pot[i - 1]);
  scanf("%d",&n);
  REP(i, n) {
    int x;
    scanf("%d",&x);
    saz.pb(x);
    pt.pb({i + 1, x});
  }

  sort(all(saz));
  saz.erase(unique(all(saz)), saz.end());

  int maks = 0;

  REP(i, (int)pt.size()) {
    pt[i].sec = lower_bound(all(saz), pt[i].sec) - saz.begin();
  }

  REP(tt, 2) {
    for (int i = (int)pt.size() - 1; i >= 0; i--) {
      if (tt) pt[i].sec = n - pt[i].sec;
      pii t = T.get(1, 0, offset - 1, 0, pt[i].sec - 1);
      if (t.fi == 0) t.sec = 1;
      t.fi++;
      T.update(pt[i].sec, t);
      dp[tt][pt[i].fi - 1] = t;
      if (tt) maks = max(maks, t.fi + dp[0][pt[i].fi - 1].fi - 1);
    }
    T.clear();
  }

  int sol = 0;
  REP(i, n) {
    if (dp[0][i].fi + dp[1][i].fi -  1 == maks) sol = add(sol, mul(dp[0][i].sec, dp[1][i].sec));
  }

  printf("%d %d\n",maks, mul(pot[n - maks], sol));
  return 0;
}

Compilation message (stderr)

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

• Subtask 1: 140 / 140