QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#434473#8781. Element-Wise Comparisonucup-team896#WA 231ms921404kbC++142.1kb2024-06-08 16:18:092024-06-08 16:18:09

Judging History

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

  • [2024-06-08 16:18:09]
  • 评测
  • 测评结果:WA
  • 用时:231ms
  • 内存:921404kb
  • [2024-06-08 16:18:09]
  • 提交

answer

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D("[Debug] "#__VA_ARGS__ " = "), \
              debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T> void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T> void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

bool me;

const int maxn = 50010;

bitset<maxn> f[maxn], o, cur, t[maxn << 1], tmp;
int n, m, a[maxn], pos[maxn], ls[maxn], rs[maxn], tot, rt;

#define mid ((l + r) >> 1)

void build(int &c, int l, int r) {
  c = ++tot, t[c].set();
  if (l == r) return;
  build(ls[c], l, mid), build(rs[c], mid + 1, r);
}

void upd(int c, int l, int r, int x, int y) {
  if (l == x && r == y) return t[c] &= tmp, void();
  if (y <= mid) upd(ls[c], l, mid, x, y);
  else if (x > mid) upd(rs[c], mid + 1, r, x, y);
  else upd(ls[c], l, mid, x, mid), upd(rs[c], mid + 1, r, mid + 1, y);
}

void solve(int c, int l, int r) {
  if (l == r) return f[l] &= t[c], void();
  t[ls[c]] &= t[c], t[rs[c]] &= t[c];
  solve(ls[c], l, mid), solve(rs[c], mid + 1, r);
}

#undef mid

bool mb;

int main() {
  cerr << (&me - &mb) / 1048576. << '\n';
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m;
  build(rt, 1, n);
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n - m) o.set(i);
  rep (i, 1, n - m) f[i] = o, o.reset(n - m - i + 1);
  rep (i, 1, n) pos[a[i]] = i;
  cur.set();
  rep (i, 1, n) {
    cur.reset(pos[i]);
    tmp = cur >> pos[i];
    upd(rt, 1, n, max(1, pos[i] - m + 1), pos[i]);
  }
  solve(rt, 1, n);
  ll ans = 0;
  rep (i, 1, n) ans += f[i].count();
  cout << ans << '\n';
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5844kb

input:

5 3
5 2 1 3 4

output:

0

result:

ok answer is '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5960kb

input:

5 2
3 1 4 2 5

output:

2

result:

ok answer is '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7972kb

input:

4 2
1 2 3 4

output:

3

result:

ok answer is '3'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5892kb

input:

4 2
4 3 2 1

output:

0

result:

ok answer is '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7936kb

input:

1 1
1

output:

0

result:

ok answer is '0'

Test #6:

score: -100
Wrong Answer
time: 231ms
memory: 921404kb

input:

50000 2
44045 29783 5389 7756 44022 45140 21967 5478 10868 49226 21775 31669 49836 13511 46116 14229 27206 31168 37389 3158 10658 41154 14635 18526 40540 6451 23197 46719 30593 13517 8604 46666 39189 43746 12778 3684 3194 36979 43020 14652 19549 31178 17144 27177 44336 2849 40220 11751 41993 32209 4...

output:

9192835

result:

wrong answer expected '310780127', found '9192835'