oj.uz

Submission #198156

# Submission time Handle Problem Language Result Execution time Memory
198156 2020-01-24T22:53:59 Z mkisic Zoltan (COCI16_zoltan) C++14
56 / 140
 459 ms 13176 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];

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);
    if (i) pt.pb({-(i + 1), x});
    pt.pb({i + 1, x});
    pt1.pb({i + 1, x});
  }

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

  sort(all(pt));
  pii ans, ans1;

  REP(i, (int)pt.size()) {
    pt[i].sec = lower_bound(all(saz), pt[i].sec) - saz.begin();
    pii t = T.get(1, 0, offset - 1, 0, pt[i].sec - 1);
    if (t.fi == 0) t.sec = 1;
    t.fi++;
    ans = T.merge(ans, t);
    T.update(pt[i].sec, t);
  }

  T.clear();
  pt = pt1;
  REP(i, (int)pt.size()) {
    pt[i].sec = lower_bound(all(saz), pt[i].sec) - saz.begin();
    pii t = T.get(1, 0, offset - 1, 0, pt[i].sec - 1);
    if (t.fi == 0) t.sec = 1;
    t.fi++;
    ans1 = T.merge(ans1, t);
    T.update(pt[i].sec, t);
  }

  int sol = ans.sec;
  //if (ans1.fi == ans.fi) sol = add(sol, -ans1.sec);
  if (ans.fi == 1) sol = n;
  printf("%d %d\n",ans.fi, mul(sol, pot[n - ans.fi]));
  return 0;
}

Compilation message

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

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5240 KB Output isn't correct
2 Correct 9 ms 5240 KB Output is correct
3 Correct 9 ms 5132 KB Output is correct
4 Correct 9 ms 5240 KB Output is correct
5 Correct 9 ms 5240 KB Output is correct
6 Correct 8 ms 5240 KB Output is correct
7 Incorrect 10 ms 5240 KB Output isn't correct
8 Incorrect 10 ms 5232 KB Output isn't correct
9 Incorrect 10 ms 5240 KB Output isn't correct
10 Incorrect 10 ms 5240 KB Output isn't correct
11 Correct 273 ms 12136 KB Output is correct
12 Correct 233 ms 12260 KB Output is correct
13 Correct 217 ms 9572 KB Output is correct
14 Incorrect 306 ms 12260 KB Output isn't correct
15 Incorrect 401 ms 12260 KB Output isn't correct
16 Incorrect 459 ms 13024 KB Output isn't correct
17 Incorrect 321 ms 13148 KB Output isn't correct
18 Incorrect 319 ms 13152 KB Output isn't correct
19 Incorrect 323 ms 13148 KB Output isn't correct
20 Incorrect 321 ms 13176 KB Output isn't correct