QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#812796#9786. Magical Bagsucup-team135#WA 0ms3852kbC++205.6kb2024-12-13 18:47:292024-12-13 18:47:32

Judging History

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

  • [2024-12-13 18:47:32]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2024-12-13 18:47:29]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define int long long
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)

template<typename T, typename U>
struct SegmentTree {
  int h, n;
  T neutral;
  U unite;
  vector<T> data;

  template<typename I>
  SegmentTree(int sz, T neutral, U unite, I init) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n) {
    for (int i = 0; i < sz; ++i) data[i + n] = init(i);
    for (int i = n - 1; i > 0; --i) data[i] = unite(data[2 * i], data[2 * i + 1]);
  }

  SegmentTree(int sz, T neutral, U unite) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n, neutral) {}

  void set(int i, T x) {
    data[i += n] = x;
    for (i /= 2; i > 0; i /= 2) data[i] = unite(data[2 * i], data[2 * i + 1]);
  }

  T get(int l, int r) {
    T leftRes = neutral, rightRes = neutral;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) leftRes = unite(leftRes, data[l++]);
      if (r & 1) rightRes = unite(data[--r], rightRes);
    }
    return unite(leftRes, rightRes);
  }
  int left(int i) {
    int lvl = __lg(i);
    return (i & ((1 << lvl) - 1)) * (1 << (h - lvl));
  }
  int right(int i) {
    int lvl = __lg(i);
    return ((i & ((1 << lvl) - 1)) + 1) * (1 << (h - lvl));
  }

  // l \in [0; n) && ok(get(l, l), l);
  // returns last r: ok(get(l, r), r)
  template<typename C>
  int lastTrue(int l, C ok) {
    T cur = neutral;
    l += n;
    do {
      l >>= __builtin_ctz(l);
      T with1 = unite(cur, data[l]);
      if (ok(with1, right(l))) {
        cur = with1;
        ++l;
      } else {
        while (l < n) {
          T with2 = unite(cur, data[2 * l]);
          if (ok(with2, right(2 * l))) {
            cur = with2;
            l = 2 * l + 1;
          } else {
            l = 2 * l;
          }
        }
        return l - n;
      }
    } while (l & (l - 1));
    return n;
  }

  // r \in [0; n) && ok(get(r, r), r);
  // returns first l: ok(get(l, r), l)
  template<typename C>
  int firstTrue(int r, C ok) {
    T cur = neutral;
    r += n;
    while (r & (r - 1)) {
      r >>= __builtin_ctz(r);
      T with1 = unite(data[--r], cur);
      if (ok(with1, left(r))) {
        cur = with1;
      } else {
        while (r < n) {
          T with2 = unite(data[2 * r + 1], cur);
          if (ok(with2, left(2 * r + 1))) {
            cur = with2;
            r = 2 * r;
          } else {
            r = 2 * r + 1;
          }
        }
        return r - n + 1;
      }
    }
    return 0;
  }
};

int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n;
    cin >> n;

    vector <vector <int> > a(n);
    vector <int> l(n), r(n), c;
    for (int i = 0; i < n; ++i) {

        int k;
        cin >> k;

        a[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> a[i][j];
        }

        l[i] = r[i] = a[i].front();
        for (int e : a[i]) {
            l[i] = min(l[i], e);
            r[i] = max(r[i], e);
        }

        c.app(l[i]);
        if (r[i] != l[i]) {
            c.app(r[i]);
        }
    }
    sort(all(c));
    int sz = c.size();
    auto compress = [&] (int &x) {
        x = lower_bound(all(c), x) - c.begin();
    };
    for (int i = 0; i < n; ++i) {
        compress(l[i]);
        compress(r[i]);
    }

    vector <int> isl(sz), isr(sz), minr(sz), maxl(sz);

    for (int i = 0; i < n; ++i) {
        isl[l[i]]=i;
        isr[r[i]]=i;
    }

    int last = sz;
    for (int i = sz - 1; i >= 0; --i) {
        if (isr[i]) {
            last = i;
        }
        minr[i] = last;
    }
    last = 0;
    for (int i = 0; i < sz; ++i) {
        if (isl[i]) {
            last = i;
        }
        maxl[i] = last;
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (l[i] == r[i]) {
            ans++;
        }
        else {
            ans += 2;
        }
    }
    vector <pair <int, int> > cand;
    for (int i = 0; i < n; ++i) {
        if (l[i] < r[i]) {

            int L = maxl[r[i]], R = minr[l[i]];
            for (int e : a[i]) {
                if (L <= e && e <= R) {
                    cand.push_back({r[i], l[i]});
                    break;
                }
            }

        }
    }

    int lastr = -1;
    for (auto [r, l] : cand) {
        if (lastr < l) {
            ans--;
            lastr = r;
        }
    }

    cout << ans << '\n';
    return 0;
}





















詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3484kb

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

input:

4
3 4 7 10
2 1 9
4 11 2 8 14
3 6 12 13

output:

7

result:

ok 1 number(s): "7"

Test #4:

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3852kb

input:

100
4 372861091 407948190 424244630 359746969
6 568180757 527358812 494745349 665803213 674832670 586694351
4 696340797 775899164 919971335 716827187
4 123145962 344250363 122030550 251739234
4 342654413 368648894 150539766 255189030
1 194505887
3 755984448 736803561 745474041
4 709314938 498953418 ...

output:

187

result:

wrong answer 1st numbers differ - expected: '177', found: '187'