QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#397899	#3299. Advertisement Matching	alpha1022	WA	2ms	12108kb	C++14	2.2kb	2024-04-24 19:27:20	2024-04-24 19:27:21

Judging History

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

[2024-04-24 19:27:21]
评测

测评结果：WA
用时：2ms
内存：12108kb

查看

[2024-04-24 19:27:20]
提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2.5e5;

int n, m;
int a[N + 5], b[N + 5], p[N + 5];
int cnt[N + 5];
ll sum[N + 5];
struct BinaryIndexedTree {
  int c[N * 2 + 5];
  void update(int x, int k) {
    for (++x; x <= N * 2; x += x & -x) c[x] += k;
  }
  int query(int x) {
    int ret = 0;
    for (++x; x; x &= x - 1) ret += c[x];
    return ret;
  }
} bit;
struct SegmentTree {
  #define ls (u << 1)
  #define rs (ls | 1)
  struct node {
    ll max; int add;
  } seg[N * 4 + 5];
  void pushUp(int u) { seg[u].max = max(seg[ls].max, seg[rs].max) + seg[u].add; }
  void apply(int k, int u) { seg[u].max += k, seg[u].add += k; }
  void update(int l, int r, int k, int u, int tl, int tr) {
    if (l > r) return ;
    if (l <= tl && tr <= r) return apply(k, u);
    int mid = (tl + tr) >> 1;
    if (l <= mid) update(l, r, k, ls, tl, mid);
    if (r > mid) update(l, r, k, rs, mid + 1, tr);
    pushUp(u);
  }
  void build(int u, int tl, int tr) {
    if (tl == tr) { seg[u].max = sum[tl]; return ; }
    int mid = (tl + tr) >> 1;
    build(ls, tl, mid), build(rs, mid + 1, tr),
    pushUp(u);
  }
  #undef ls
  #undef rs
} seg;

int q;

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i), p[i] = i, bit.update(a[i], 1);
  sort(p + 1, p + n + 1, [](int x, int y) { return a[x] > a[y]; });
  for (int i = 1; i <= n; ++i) sum[i] += a[p[i]];
  for (int i = 1; i <= m; ++i) scanf("%d", b + i), ++cnt[b[i]], sum[b[i]] -= b[i];
  for (int i = N - 1; i; --i) cnt[i] += cnt[i + 1];
  for (int i = 1; i <= n; ++i) sum[i + 1] += sum[i];
  for (int i = 1; i <= n; ++i) sum[i] -= (ll)cnt[i + 1] * i;
  seg.build(1, 1, n);
  for (scanf("%d", &q); q; --q) {
    int op, x; scanf("%d%d", &op, &x);
    if (op == 1)
      bit.update(a[x], -1), bit.update(++a[x], 1),
      seg.update(bit.query(a[x]), n, 1, 1, 1, n);
    else if (op == 2)
      seg.update(bit.query(a[x]), n, -1, 1, 1, n),
      bit.update(a[x], -1), bit.update(--a[x], 1);
    else if (op == 3) seg.update(++b[x], n, -1, 1, 1, n);
    else seg.update(b[x]--, n, 1, 1, 1, n);
    printf("%d\n", (int)(seg.seg[1].max <= 0));
  }
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 12096kb

input:

output:

result:

ok 5 lines

Test #2:

score: 0

Accepted

time: 2ms

memory: 12108kb

input:

100 100
13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 1...

output:

result:

ok 100 lines

Test #3:

score: -100

Wrong Answer

time: 2ms

memory: 12096kb

input:

100 100
42 28 42 64 42 29 72 64 72 29 28 72 28 72 29 42 64 42 72 29 64 29 72 28 42 64 72 64 28 42 72 42 29 64 72 64 72 29 72 29 64 42 64 72 29 28 42 64 72 64 72 28 42 64 64 42 64 64 28 28 72 29 28 64 28 64 64 72 64 28 42 29 64 42 64 42 72 64 64 64 28 64 42 72 64 29 64 29 64 64 72 29 29 28 42 72 64 7...

output:

result:

wrong answer 2nd lines differ - expected: '0', found: '1'