oj.uz

Submission #198155

# Submission time Handle Problem Language Result Execution time Memory
198155 2020-01-24T22:51:53 Z mkisic Zoltan (COCI16_zoltan) C++14
49 / 140
 464 ms 13148 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);
  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
49.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5240 KB Output isn't correct
2 Correct 10 ms 5240 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 8 ms 5240 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Incorrect 8 ms 5152 KB Output isn't 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 5240 KB Output isn't correct
10 Incorrect 10 ms 5240 KB Output isn't correct
11 Correct 275 ms 12260 KB Output is correct
12 Correct 240 ms 12260 KB Output is correct
13 Correct 220 ms 9572 KB Output is correct
14 Incorrect 315 ms 12232 KB Output isn't correct
15 Incorrect 410 ms 12356 KB Output isn't correct
16 Incorrect 464 ms 13020 KB Output isn't correct
17 Incorrect 361 ms 13148 KB Output isn't correct
18 Incorrect 327 ms 13076 KB Output isn't correct
19 Incorrect 334 ms 13148 KB Output isn't correct
20 Incorrect 326 ms 13020 KB Output isn't correct