QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640701 | #6258. Find my Family | dohoon# | WA | 88ms | 17632kb | C++17 | 2.0kb | 2024-10-14 15:22:42 | 2024-10-14 15:22:43 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,a,b) for (ll i = (a); i <= (b); ++i)
#define per(i,a,b) for (ll i = (b); i >= (a); --i)
#define all(x) begin(x),end(x)
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using ii = pair<ll,ll>;
ll k;
vi ans;
const ll N = 3e5+3, INF = 1e9+3;
ll n, a[N];
template <const ll N>
struct seg {
ll n, mn[2*N], mx[2*N];
void set(ll _n) {
n = _n;
fill(mn,mn+2*n,+INF);
fill(mx,mx+2*n,-INF);
}
void update(ll k, ll x) {
k+=n; mn[k] = mx[k] = x;
for (; (k/=2) >= 1; k /= 2) {
mn[k] = min(mn[2*k], mn[2*k+1]);
mx[k] = max(mx[2*k], mx[2*k+1]);
}
}
ii query(ll l, ll r) {
ll mres = +INF, Mres = -INF;
for (l+=n, r+=n; l <= r; ++l/=2, --r/=2) {
if (l&1) {
mres = min(mres, mn[l]);
Mres = max(Mres, mx[l]);
}
if (~r&1) {
mres = min(mres, mn[r]);
Mres = max(Mres, mx[r]);
}
}
return { mres, Mres };
}
};
seg<N> ds;
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k;
rep(tc,1,k) {
cin >> n;
vi vals;
rep(i,1,n) cin >> a[i], vals.pb(a[i]);
sort(all(vals)), vals.erase(unique(all(vals)),end(vals));
ds.set(n+1);
per(i,1,n) {
auto j = lower_bound(all(vals), a[i]) - begin(vals);
ds.update(j, i);
ll mn = ds.query(0, j-1).first;
ll mx = ds.query(j+1, n).second;
// cerr << tc << endl;
// cerr << i << ' ' << mn << ' ' << mx << endl;
if (mn == +INF) continue;
if (mx == -INF) continue;
if (mn < mx) {
ans.push_back(tc);
break;
}
}
}
cout << size(ans) << '\n';
for (auto e : ans) {
cout << e << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7708kb
input:
1 3 2 1 3
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 7628kb
input:
4 4 140 157 160 193 5 15 24 38 9 30 6 36 12 24 29 23 15 6 170 230 320 180 250 210
output:
2 2 4
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 88ms
memory: 17404kb
input:
1 271273 43747 45949 45991 59771 62951 78721 90843 96669 105382 125056 190481 223823 234273 241140 245677 331310 332730 342496 346873 364619 374954 395547 396228 402197 405521 425867 463937 465115 480404 509574 527742 529523 531604 542717 555276 567633 607526 642706 675568 702732 726193 728907 74120...
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 38ms
memory: 16976kb
input:
1 278011 727061307 368308202 520895620 233571177 962866275 741680843 264488440 68105796 948966820 466360363 79235752 189876633 279183294 707022089 551954537 533095838 391251801 821128899 372263578 515707123 232234930 644859992 86801330 757154237 807459900 586448507 672723131 452745534 295498461 6162...
output:
1 1
result:
ok 2 lines
Test #5:
score: -100
Wrong Answer
time: 82ms
memory: 17632kb
input:
179 6 172113495 59803164 782209477 34402441 69284247 650685671 5 985712353 368711252 482009833 526445043 916859899 4 590307238 387574595 458391611 853071135 5 955235353 236771554 596823814 599387985 431401542 5 671335527 489612401 642100211 68409147 878368953 6 221011605 485556690 458137100 74629254...
output:
97 1 3 5 6 8 9 13 14 15 18 20 21 23 25 27 30 34 36 37 38 39 44 46 48 49 50 51 52 53 56 57 62 64 67 68 69 70 71 72 73 74 75 77 81 83 84 86 87 89 91 93 94 95 96 97 100 101 103 110 111 115 116 117 118 121 124 130 131 133 134 135 136 137 138 140 141 143 145 148 149 151 152 155 156 157 158 161 162 163 16...
result:
wrong answer 1st lines differ - expected: '111', found: '97'