oj.uz

Submission #198158

# Submission time Handle Problem Language Result Execution time Memory
198158 2020-01-24T23:10:07 Z mkisic Zoltan (COCI16_zoltan) C++14
42 / 140
 290 ms 10972 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(tt, 2) {
    REP(i, (int)pt.size()) {
      if (!tt) pt[i].sec = lower_bound(all(saz), pt[i].sec) - saz.begin();
      if (!tt) pt[i].sec = 200000 - 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;
      maks = max(maks, t.fi + dp[tt ^ 1][pt[i].fi - 1].fi - 1);
    }
    reverse(all(pt));
    T.clear();
  }

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

  printf("%d %d\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
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5240 KB Output isn't correct
2 Incorrect 9 ms 5240 KB Output isn't correct
3 Incorrect 9 ms 5240 KB Output isn't correct
4 Correct 9 ms 5240 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct
6 Correct 9 ms 5240 KB Output is correct
7 Incorrect 10 ms 5240 KB Output isn't correct
8 Incorrect 10 ms 5240 KB Output isn't correct
9 Incorrect 10 ms 5244 KB Output isn't correct
10 Incorrect 10 ms 5240 KB Output isn't correct
11 Correct 176 ms 9824 KB Output is correct
12 Correct 154 ms 9184 KB Output is correct
13 Correct 144 ms 8948 KB Output is correct
14 Incorrect 198 ms 9180 KB Output isn't correct
15 Incorrect 251 ms 10176 KB Output isn't correct
16 Incorrect 290 ms 10844 KB Output isn't correct
17 Incorrect 217 ms 10848 KB Output isn't correct
18 Incorrect 220 ms 10932 KB Output isn't correct
19 Incorrect 220 ms 10972 KB Output isn't correct
20 Incorrect 222 ms 10848 KB Output isn't correct