QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812796 | #9786. Magical Bags | ucup-team135# | WA | 0ms | 3852kb | C++20 | 5.6kb | 2024-12-13 18:47:29 | 2024-12-13 18:47:32 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
#include <array>
#include <functional>
#include <stack>
#include <memory>
using namespace std;
#define int long long
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)
template<typename T, typename U>
struct SegmentTree {
int h, n;
T neutral;
U unite;
vector<T> data;
template<typename I>
SegmentTree(int sz, T neutral, U unite, I init) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n) {
for (int i = 0; i < sz; ++i) data[i + n] = init(i);
for (int i = n - 1; i > 0; --i) data[i] = unite(data[2 * i], data[2 * i + 1]);
}
SegmentTree(int sz, T neutral, U unite) : h(__lg(sz) + 1), n(1 << h), neutral(neutral), unite(unite), data(2 * n, neutral) {}
void set(int i, T x) {
data[i += n] = x;
for (i /= 2; i > 0; i /= 2) data[i] = unite(data[2 * i], data[2 * i + 1]);
}
T get(int l, int r) {
T leftRes = neutral, rightRes = neutral;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) leftRes = unite(leftRes, data[l++]);
if (r & 1) rightRes = unite(data[--r], rightRes);
}
return unite(leftRes, rightRes);
}
int left(int i) {
int lvl = __lg(i);
return (i & ((1 << lvl) - 1)) * (1 << (h - lvl));
}
int right(int i) {
int lvl = __lg(i);
return ((i & ((1 << lvl) - 1)) + 1) * (1 << (h - lvl));
}
// l \in [0; n) && ok(get(l, l), l);
// returns last r: ok(get(l, r), r)
template<typename C>
int lastTrue(int l, C ok) {
T cur = neutral;
l += n;
do {
l >>= __builtin_ctz(l);
T with1 = unite(cur, data[l]);
if (ok(with1, right(l))) {
cur = with1;
++l;
} else {
while (l < n) {
T with2 = unite(cur, data[2 * l]);
if (ok(with2, right(2 * l))) {
cur = with2;
l = 2 * l + 1;
} else {
l = 2 * l;
}
}
return l - n;
}
} while (l & (l - 1));
return n;
}
// r \in [0; n) && ok(get(r, r), r);
// returns first l: ok(get(l, r), l)
template<typename C>
int firstTrue(int r, C ok) {
T cur = neutral;
r += n;
while (r & (r - 1)) {
r >>= __builtin_ctz(r);
T with1 = unite(data[--r], cur);
if (ok(with1, left(r))) {
cur = with1;
} else {
while (r < n) {
T with2 = unite(data[2 * r + 1], cur);
if (ok(with2, left(2 * r + 1))) {
cur = with2;
r = 2 * r;
} else {
r = 2 * r + 1;
}
}
return r - n + 1;
}
}
return 0;
}
};
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin >> n;
vector <vector <int> > a(n);
vector <int> l(n), r(n), c;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
a[i].resize(k);
for (int j = 0; j < k; ++j) {
cin >> a[i][j];
}
l[i] = r[i] = a[i].front();
for (int e : a[i]) {
l[i] = min(l[i], e);
r[i] = max(r[i], e);
}
c.app(l[i]);
if (r[i] != l[i]) {
c.app(r[i]);
}
}
sort(all(c));
int sz = c.size();
auto compress = [&] (int &x) {
x = lower_bound(all(c), x) - c.begin();
};
for (int i = 0; i < n; ++i) {
compress(l[i]);
compress(r[i]);
}
vector <int> isl(sz), isr(sz), minr(sz), maxl(sz);
for (int i = 0; i < n; ++i) {
isl[l[i]]=i;
isr[r[i]]=i;
}
int last = sz;
for (int i = sz - 1; i >= 0; --i) {
if (isr[i]) {
last = i;
}
minr[i] = last;
}
last = 0;
for (int i = 0; i < sz; ++i) {
if (isl[i]) {
last = i;
}
maxl[i] = last;
}
int ans = 0;
for (int i = 0; i < n; ++i) {
if (l[i] == r[i]) {
ans++;
}
else {
ans += 2;
}
}
vector <pair <int, int> > cand;
for (int i = 0; i < n; ++i) {
if (l[i] < r[i]) {
int L = maxl[r[i]], R = minr[l[i]];
for (int e : a[i]) {
if (L <= e && e <= R) {
cand.push_back({r[i], l[i]});
break;
}
}
}
}
int lastr = -1;
for (auto [r, l] : cand) {
if (lastr < l) {
ans--;
lastr = r;
}
}
cout << ans << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3484kb
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: 3596kb
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: 3536kb
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: 3528kb
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: 3852kb
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:
187
result:
wrong answer 1st numbers differ - expected: '177', found: '187'