oj.uz

Submission #198159

# Submission time Handle Problem Language Result Execution time Memory
198159 2020-01-24T23:40:53 Z mkisic Zoltan (COCI16_zoltan) C++14
140 / 140
 272 ms 11020 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5240 KB Output is correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 9 ms 5240 KB Output is correct
4 Correct 9 ms 5240 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Correct 10 ms 5240 KB Output is correct
8 Correct 10 ms 5236 KB Output is correct
9 Correct 10 ms 5240 KB Output is correct
10 Correct 10 ms 5212 KB Output is correct
11 Correct 168 ms 9804 KB Output is correct
12 Correct 146 ms 9312 KB Output is correct
13 Correct 137 ms 8976 KB Output is correct
14 Correct 188 ms 9176 KB Output is correct
15 Correct 235 ms 10208 KB Output is correct
16 Correct 272 ms 10976 KB Output is correct
17 Correct 206 ms 10976 KB Output is correct
18 Correct 204 ms 11020 KB Output is correct
19 Correct 246 ms 10944 KB Output is correct
20 Correct 211 ms 10976 KB Output is correct