QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#776128#9786. Magical Bagsucup-team191#WA 1ms5656kbC++231.7kb2024-11-23 17:39:402024-11-23 17:39:41

Judging History

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

  • [2024-11-23 17:39:41]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5656kb
  • [2024-11-23 17:39:40]
  • 提交

answer

#include <bits/stdc++.h>
#define X first
#define Y second
#define PB push_back
#define x first
#define y second
#define pb push_back
using namespace std;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
using pii=pair<int,int>;
#define all(a) begin(a),end(a)

const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;

int n, L[N], R[N], red[N];
vector<pii> v;
vector<int> saz;
int loga[N], uzeo[N];

void add(int x) {
	for(x++; x < N; x += x & -x) loga[x]++;
}

int get(int x) {
	int ret = 0;
	for(x++; x ; x -= x & -x) ret += loga[x];
	return ret;
}

bool cmp(int A, int B) {
	return R[A] < R[B];
}

bool cmp2(int A, int B) {
	return L[A] < L[B];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int k; cin >> k;
		vi a(k);
		for (int j = 0; j < k; ++j) cin >> a[j];
		sort(a.begin(), a.end());
		L[i] = a[0], R[i] = a.back();
		saz.PB(L[i]), saz.PB(R[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 0;i < n;i++) {
		L[i] = lower_bound(saz.begin(), saz.end(), L[i]) - saz.begin();
		R[i] = lower_bound(saz.begin(), saz.end(), R[i]) - saz.begin();
		red[i] = i;
	}
	sort(red, red + n, cmp);
	for(int i = 0;i < n;i++) {
		int x = red[i];
		if(get(L[x]) != i) {
			uzeo[x] = 1;
		}
		add(L[x]);
	}
	int sol = 0;
	vector < int > jos;
	for(int i = 0;i < n;i++) {
		if(!uzeo[i]) {
			if(L[i] != R[i]) jos.PB(i);
			else sol++;
		}
	}
	sort(jos.begin(), jos.end(), cmp2);
	int dos = -1;
	for(int x : jos) {
		if(dos < L[x]) {
			dos = R[x]; sol++;
		}
	}
	cout << 2 * n - sol << endl;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
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: 3892kb

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

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

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

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:

175

result:

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