QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#801719#9786. Magical Bagsucup-team1430#WA 0ms3832kbC++201.6kb2024-12-07 06:35:242024-12-07 06:35:25

Judging History

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

  • [2024-12-07 06:35:25]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-12-07 06:35:24]
  • 提交

answer

#include<bits/stdc++.h>

#define endl '\n'
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cout << #x << ": " << x << endl
// #define debug(...) 
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)((x).size())
#define esp ' '
#define pii pair<int,int>
#define vi vector<int>

typedef long long ll;
const int oo = 1e9+1;

using namespace std;

void solve() {
	int n; cin >> n;
	vector<pair<int, int>> rgs(n);
	vector<int> ls(n), rs(n);
	int ans = 0;
	int sum = 0;
	rep(i, 0, n) {
		int k; cin >> k;
		sum += k;
		int minv = oo;
		int maxv = -oo;
		rep(j, 0, k) {
			int x; cin >> x;
			minv = min(minv, x);
			maxv = max(maxv, x);
		}
		ans += k -2;
		if (minv == maxv) ans++;
		rgs[i] = {minv, maxv};
		ls[i] = minv;
		rs[i] = maxv;
	}
	sort(all(rgs));
	sort(all(ls));
	sort(all(rs));

	auto query = [&](int l, int r, const vector<int> & v) {
		int bigr = lower_bound(all(v), r) - v.begin();
		int small = upper_bound(all(v), l) - v.begin();
		return max(bigr - small, 0);
	};

	vector<int> dp(n+1, 0);

	dp[n] = 0;
	for (int i = n-1; i >= 0; i--) {
		int nxt = upper_bound(all(rgs), pair{rgs[i].second +1, (int)-1}) - rgs.begin();
		dp[i] = dp[i+1];
		if (rgs[i].first == rgs[i].second) continue;
		if (query(rgs[i].first, rgs[i].second, ls) == 0) {
			dp[i] = max(dp[i], 1 + dp[nxt]);
		}
		if (query(rgs[i].first, rgs[i].second, rs) == 0) {
			dp[i] = max(dp[i], 1 + dp[nxt]);
		}
	}
	// debug(ans);
	// debug(dp[0]);

	cout << sum - (dp[0] + ans) << endl;

}

signed main() {
	ios_base::sync_with_stdio(0);cin.tie(0);

	int t=1;
	//cin>>t;
	while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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'