QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640701#6258. Find my Familydohoon#WA 88ms17632kbC++172.0kb2024-10-14 15:22:422024-10-14 15:22:43

Judging History

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

  • [2024-10-14 15:22:43]
  • 评测
  • 测评结果:WA
  • 用时:88ms
  • 内存:17632kb
  • [2024-10-14 15:22:42]
  • 提交

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'