QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#329513#8218. 水镜yzy10 1ms5836kbC++173.2kb2024-02-16 20:22:012024-02-16 20:22:01

Judging History

你现在查看的是最新测评结果

  • [2024-02-16 20:22:01]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:5836kb
  • [2024-02-16 20:22:01]
  • 提交

answer

#include <bits/stdc++.h>

#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#else
#define dbg(x...) (0)
#endif

using namespace std;

using ll = long long;

// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))

template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
  if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
  if (y < x) x = y;
}

const int N = 1e6 + 9;
int n, R[N];
ll a[N];

struct Node {
  int l;
  mutable int r;
  mutable char typ;
};

inline bool operator<(Node x, Node y) { return x.l < y.l; }

multiset<Node> S;
map<int, vector<int>> mp;

inline void Upd(multiset<Node>::iterator it) {
  if (it->typ != '=') up(R[it->l], it->r + 1);
  auto it1 = next(it);
  if (it1 == S.end()) return;
  if (it->typ == '>') {
    if (it1->typ == '<')
      up(R[it->l], it1->r + 1);
    else if (auto it2 = next(it1); it2 != S.end() && it1->l == it1->r && it2->typ == '<') {
      up(R[it->l], it2->r + 1);
      // dbg(R[it->l], S[i + 2].r + 1);
    } else
      up(R[it->l], it->r + 2);
  } else if (it1->typ == '<')
    up(R[it->r], it1->r + 1);
}

inline char Cmp(ll x, ll y) {
  if (x < y) return '<';
  if (x == y) return '=';
  return '>';
}

inline void Cha(int p, char typ) {
  auto it = prev(S.upper_bound({p, 0, 0}));
  auto bak = *it;
  S.erase(it);
  if (bak.l <= p - 1) S.insert({bak.l, p - 1, bak.typ});
  if (p + 1 <= bak.r) S.insert({p + 1, bak.r, bak.typ});
  it = S.insert({p, p, typ});
  if (it != S.begin() && prev(it)->typ == typ) {
    bak = *prev(it);
    S.erase(prev(it)), S.erase(it);
    it = S.insert({bak.l, p, typ});
  }
  if (next(it) != S.end() && next(it)->typ == typ) {
    bak = *next(it);
    S.erase(next(it)), S.erase(it);
    it = S.insert({p, bak.r, typ});
  }
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  re (i, n) cin >> a[i], a[i] <<= 1;
  re (i, n - 1) R[i] = i + 1;
  re (i, n - 1) {
    char typ = Cmp(a[i], a[i + 1]);
    if (S.empty() || S.rbegin()->typ != typ)
      S.insert({i, i, typ});
    else
      ++S.rbegin()->r;
  }
  for (auto it = S.begin(); it != S.end(); ++it) Upd(it);
  re (i, n - 1) mp[a[i] + a[i + 1]].push_back(i), mp[a[i] + a[i + 1] + 1].push_back(i);
  for (auto [x, vec] : mp) {
    for (auto y : vec) {
      Cha(y, Cmp(max(a[y], x - a[y]), max(a[y + 1], x - a[y + 1])));
    }
    for (auto y : vec) {
      auto it = prev(S.upper_bound({y, 0, 0}));
      re (_, 3) {
        Upd(it);
        if (it == S.begin()) break;
        --it;
      }
    }
  }
  ll ans = 0;
  rep (i, 2, n - 1) up(R[i], R[i - 1]);
  // re (i, n - 1) cerr << R[i] << " \n"[i == edi];
  re (i, n - 1) ans += R[i] - i;
  cout << ans << '\n';
  return 0;
}

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 7
Accepted
time: 1ms
memory: 5836kb

input:

2
2 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: -7
Runtime Error

input:

10
2 2 2 2 1 4 5 3 3 2

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%