QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#776128 | #9786. Magical Bags | ucup-team191# | WA | 1ms | 5656kb | C++23 | 1.7kb | 2024-11-23 17:39:40 | 2024-11-23 17:39:41 |
Judging History
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'