QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#775220#9786. Magical Bagsucup-team896#WA 2ms7792kbC++202.1kb2024-11-23 15:04:322024-11-23 15:04:33

Judging History

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

  • [2024-11-23 15:04:33]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7792kb
  • [2024-11-23 15:04:32]
  • 提交

answer

// Author: Klay Thompson
// Problem: F. Magical Bags
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

#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>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 200010;

int n, m, sz, c[maxn], vis[maxn], mn[maxn];
pii a[maxn], b[maxn];

bool check(int x, int y) {
  if (b[x].fi >= b[y].se) return false;
  if (b[y].fi >= b[x].se) return false;
  return true;
}

int g(pii x) {
  return x.fi == x.se ? 1 : 2;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n;
  rep (i, 1, n) {
    cin >> sz;
    rep (j, 1, sz) cin >> c[j];
    a[i].fi = *min_element(c + 1, c + sz + 1);
    a[i].se = *max_element(c + 1, c + sz + 1);
  }
  sort(a + 1, a + n + 1);
  mn[n + 1] = 1e9;
  per (i, n, 1) mn[i] = min(mn[i + 1], a[i].se);
  int pos = 1, ans = 0;
  rep (i, 1, n) {
    while (pos <= n && a[pos].fi <= a[i].fi) pos++;
    vis[i] = (mn[pos] < a[i].se), ans += 2 * vis[i];
  }
  rep (i, 1, n) if (!vis[i]) b[++m] = a[i];
  // rep (i, 1, m) cerr << b[i].fi << " " << b[i].se << '\n';
  for (int l = 1, r; l <= m; l = r + 1) {
    r = l;
    while (r < m && b[r + 1].fi < b[l].se) r++;
    if (l == r) {
      ans += g(b[l]);
    } else {
      int x = l, y = r;
      rep (i, l, r) if (b[i].fi == b[l].fi && b[i].se < b[x].se) x = i;
      rep (i, l, r) if (b[i].se == b[r].se && b[i].fi > b[y].fi) y = i;
      rep (i, l, r) if (i != x && i != y) ans += g(b[i]);
      if (check(x, y)) ans += g(b[x]) + g(b[y]) - min(1, g(b[x]) - 1 + g(b[y]) - 1);
      else ans += g(b[x]) + g(b[y]) - min(1, g(b[x]) - 1) - min(1, g(b[y]) - 1);
    }
  }
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7792kb

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

input:

4
1 1
1 2
1 3
1 4

output:

4

result:

ok 1 number(s): "4"

Test #3:

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

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: 1ms
memory: 7784kb

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: 1ms
memory: 7792kb

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:

186

result:

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