QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#434709#8781. Element-Wise Comparisonucup-team896#TL 351ms921648kbC++142.1kb2024-06-08 17:06:262024-06-08 17:06:30

Judging History

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

  • [2024-06-08 17:06:30]
  • 评测
  • 测评结果:TL
  • 用时:351ms
  • 内存:921648kb
  • [2024-06-08 17:06:26]
  • 提交

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 << 1], rs[maxn << 1], 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: 6180kb

input:

5 3
5 2 1 3 4

output:

0

result:

ok answer is '0'

Test #2:

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

input:

5 2
3 1 4 2 5

output:

2

result:

ok answer is '2'

Test #3:

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

input:

4 2
1 2 3 4

output:

3

result:

ok answer is '3'

Test #4:

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

input:

4 2
4 3 2 1

output:

0

result:

ok answer is '0'

Test #5:

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

input:

1 1
1

output:

0

result:

ok answer is '0'

Test #6:

score: 0
Accepted
time: 351ms
memory: 921648kb

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:

310780127

result:

ok answer is '310780127'

Test #7:

score: 0
Accepted
time: 319ms
memory: 921580kb

input:

50000 2
44015 31580 38779 29675 3269 12273 40322 471 4551 44568 21486 17093 43442 11483 9686 39913 36953 47673 34066 4943 28304 34228 9197 43349 1974 32227 8177 33236 24942 42131 34294 48071 17452 9633 18281 13817 27423 9880 15629 6991 20035 13601 39212 33548 8865 39161 48449 22164 36815 28852 43065...

output:

317708201

result:

ok answer is '317708201'

Test #8:

score: 0
Accepted
time: 308ms
memory: 921500kb

input:

50000 2
45828 16955 24033 12988 15675 6086 482 27940 30132 39389 14266 35347 46159 8317 24605 9737 30077 32664 6326 43387 7896 17806 20481 8573 8438 36474 33708 42437 8187 12300 13318 48764 34683 14983 40909 34874 47938 31131 12519 21122 22457 21062 32953 47733 46731 18062 1061 28388 27032 47303 390...

output:

309719539

result:

ok answer is '309719539'

Test #9:

score: 0
Accepted
time: 295ms
memory: 921492kb

input:

50000 2
17900 11121 24441 14321 9486 32843 40283 49359 21526 27801 47381 11444 24372 25999 16187 49470 11724 21419 31873 49053 47656 4516 33567 25021 42444 36150 1362 3711 31260 49923 19998 7275 2927 29522 40437 39439 30777 6413 17107 30917 48362 29997 47038 23951 25835 23665 2875 18889 10610 26400 ...

output:

313258830

result:

ok answer is '313258830'

Test #10:

score: 0
Accepted
time: 294ms
memory: 921500kb

input:

50000 2
29869 3482 18962 41513 1378 27297 29435 6651 12343 3742 27703 32031 15628 16084 12571 1726 30037 31904 2642 817 26607 21749 34528 33044 39980 26798 41826 37079 2809 33387 10169 47346 8551 24214 40572 43065 41730 32281 16630 47892 48890 34159 12884 8185 38452 15606 19304 8428 24230 31397 2232...

output:

313582202

result:

ok answer is '313582202'

Test #11:

score: -100
Time Limit Exceeded

input:

50000 25
24181 9781 31983 1958 1472 39943 17049 26890 16005 42039 40012 41453 7508 47251 35614 5522 27201 31665 6000 49393 17743 30487 44282 1097 39409 39745 43972 13876 33786 40423 41046 227 44642 27611 9775 21229 48475 7795 32834 15085 44154 45504 26464 45685 42844 44948 26372 30941 8490 8094 4343...

output:

58

result: