QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785219#9786. Magical BagsasxziillWA 1ms3780kbC++231.6kb2024-11-26 17:11:532024-11-26 17:12:03

Judging History

This is the latest submission verdict.

  • [2024-11-26 17:12:03]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3780kb
  • [2024-11-26 17:11:53]
  • Submitted

answer

#include <bits/stdc++.h>

using ll = long long;


void solve() {
  int n;
  std::cin >> n;
  std::vector<std::pair<int, int>> seg;
  std::map<int, std::set<int>> l, r;  
  for (int i = 0; i < n; i++) {
    std::vector<int> a;
    int k;
    std::cin >> k;
    for (int j = 0; j < k; j++) {
      int x;
      std::cin >> x;
      a.push_back(x);
    }
    std::sort(a.begin(), a.end());

    seg.emplace_back(a[0], a.back());
    l[a[0]].insert(i);
    r[a.back()].insert(i);
  } 
  //右端点能不能去掉: 存在区间[L, R] l <= L < r
  //左端点能不能去掉: 存在区间[L, R] l < R <= r

  int cnt = 0;
  for (int i = 0; i < n; i++) {
    auto &[L, R] = seg[i];
    if (R == L) {
      continue;
    }

    l[L].erase(i);
    if (l[L].empty()) {
      l.erase(L);
    }
    r[R].erase(i);
    if (r[R].empty()) {
      r.erase(R);
    }

    auto it = l.lower_bound(L);
    if (it == l.end() || it->first >= R) {
      r[R].erase(i);
      if (r[R].empty()) {
        r.erase(R);
      }
      R = L;

      l[L].insert(i);
      r[R].insert(i);
      continue;
    }

    it = r.upper_bound(L);
    if (it == r.end() || it->first > R) {
      l[L].erase(i);
      if (l[L].empty()) {
        l.erase(L);
      }
      L = R;

      l[L].insert(i);
      r[R].insert(i);
      continue;
    }

    l[L].insert(i);
    r[R].insert(i);
    cnt++;
  }

  std::cout << n + cnt;
}


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  // int t;
  // std::cin >> t;
  // while (t--) {
  //   solve();
  // }    
  solve();
  return 0;
}


詳細信息

Test #1:

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

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

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

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

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

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'