QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#775501#9786. Magical Bagsucup-team896#WA 2ms15924kbC++203.4kb2024-11-23 16:06:052024-11-23 16:06:07

Judging History

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

  • [2024-11-23 16:06:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:15924kb
  • [2024-11-23 16:06:05]
  • 提交

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 = 500010;

int n, m, sz, c[maxn], vis[maxn], mn[maxn], d[maxn], tot;
int mnp[maxn], mxp[maxn];
pii a[maxn], b[maxn];
// map<int, int> mnp, mxp;
map<pii, int> cnt;

bool check(pii x, pii y) {
  if (x.fi >= y.se) return false;
  if (y.fi >= 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);
    d[++tot] = a[i].fi, d[++tot] = a[i].se;
  }
  sort(d + 1, d + tot + 1), tot = unique(d + 1, d + tot + 1) - d - 1;
  rep (i, 1, n) a[i].fi = lower_bound(d + 1, d + tot + 1, a[i].fi) - d;
  rep (i, 1, n) a[i].se = lower_bound(d + 1, d + tot + 1, a[i].se) - d;
  rep (i, 1, n) cnt[a[i]]++;
  sort(a + 1, a + n + 1);
  rep (i, 0, tot + 1) mnp[i] = 1e9, mxp[i] = 0;
  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];
    if (vis[i]) {
      chkmn(mnp[a[i].fi], a[i].fi);
      chkmx(mxp[a[i].se], a[i].se);
      // if (!mnp.count(a[i].se)) mnp[a[i].se] = 1;
      // if (!mxp.count(a[i].fi)) mxp[a[i].fi] = 1;
    }
  }
  per (i, tot, 1) chkmn(mnp[i], mnp[i + 1]);
  rep (i, 1, tot) chkmx(mxp[i], mxp[i - 1]);
  rep (i, 1, n) if (!vis[i]) b[++m] = a[i];
  for (int l = 1, r; l <= m; l = r + 1) {
    r = l;
    while (r < m && b[r + 1].fi < b[r].se) r++;
    // rep (i, l, r) cerr << b[i].fi << " " << b[i].se << '\n';
    // cerr << "----\n";
    if (l == r) {
      if (b[l].fi == b[l].se) ans += 1;
      else if (b[l].se <= mnp[b[l].fi] || b[l].fi >= mxp[b[l].se]) ans += 1;
      else ans += 2;
    } 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) ans += g(b[i]);
      int canx = b[x].fi >= mxp[b[x].se], cany = b[y].se <= mnp[b[y].fi];
      // cerr << canx << " " << cany << endl;
      if (cnt[b[x]] >= 2) canx = 0;
      if (cnt[b[y]] >= 2) cany = 0;
      rep (i, l, r) if (i != x && i != y) canx &= (check(b[x], b[i]) == check(pii(b[x].se, b[x].se), b[i]));
      rep (i, l, r) if (i != x && i != y) cany &= (check(b[y], b[i]) == check(pii(b[y].fi, b[y].fi), b[i]));
      if (check(b[x], b[y])) {
        if (canx && check(pii(b[x].se, b[x].se), b[y])) ans--;
        else if (cany && check(b[x], pii(b[y].fi, b[y].fi))) ans--;
      } else {
        ans -= canx + cany;
      }
    }
  }
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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'