oj.uz

Submission #198157

# Submission time Handle Problem Language Result Execution time Memory
198157 2020-01-24T23:00:18 Z mkisic Zoltan (COCI16_zoltan) C++14
56 / 140
 479 ms 13292 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;
  ans = ans1 = {0, 0};
  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 7 ms 5240 KB Output isn't correct
2 Correct 8 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 8 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 11 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 270 ms 12180 KB Output is correct
12 Correct 234 ms 12260 KB Output is correct
13 Correct 220 ms 9572 KB Output is correct
14 Incorrect 314 ms 12260 KB Output isn't correct
15 Incorrect 415 ms 12252 KB Output isn't correct
16 Incorrect 479 ms 13148 KB Output isn't correct
17 Incorrect 322 ms 13020 KB Output isn't correct
18 Incorrect 321 ms 13292 KB Output isn't correct
19 Incorrect 352 ms 13052 KB Output isn't correct
20 Incorrect 324 ms 13020 KB Output isn't correct