QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812705#9786. Magical Bagsucup-team135#WA 1ms3624kbC++205.8kb2024-12-13 18:05:442024-12-13 18:05:45

Judging History

This is the latest submission verdict.

  • [2024-12-13 18:05:45]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3624kb
  • [2024-12-13 18:05:44]
  • Submitted

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 <int> l(n), r(n), c;
    for (int i = 0; i < n; ++i) {

        int k;
        cin >> k;
        cin >> l[i];
        r[i] = l[i];
        for (int j = 0; j < k - 1; ++j) {
            int x;
            cin >> x;
            l[i] = min(l[i], x);
            r[i] = max(r[i], x);
        }
        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]);
    }

    SegmentTree maxr(sz, -(int)1e18,  [](int x, int y) { return max(x, y); });
    SegmentTree maxl(sz, -(int)1e18,  [](int x, int y) { return max(x, y); });
    SegmentTree minl(sz, (int)1e18,  [](int x, int y) { return min(x, y); });
    SegmentTree minr(sz, (int)1e18,  [](int x, int y) { return min(x, y); });

    for (int i = 0; i < n; ++i) {
        maxr.set(l[i], r[i]);
        maxl.set(r[i], l[i]);
        minl.set(r[i], l[i]);
        minr.set(l[i], r[i]);
    }

    vector <int> used(n);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (l[i] == r[i]) {
            used[i] = 1;
            ans++;
        }
        else if (minr.get(l[i] + 1, r[i]) < r[i] || maxl.get(l[i] + 1, r[i]) > l[i] ||
                 (minl.get(l[i] + 1, r[i]) < l[i] && maxr.get(l[i] + 1, r[i]) > r[i])) {
                 used[i] = 1;
                 ans += 2;

                 }
    }

    SegmentTree newmaxr(sz, -(int)1e18,  [](int x, int y) { return max(x, y); });

    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            newmaxr.set(l[i], r[i]);
        }
    }

    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            if (newmaxr.get(l[i] + 1, r[i]) > r[i]) {
                ans += 2;
            }
            else {
                ans++;
            }
        }
    }



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





















Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3620kb

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: 3528kb

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: 3624kb

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:

178

result:

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