提交记录 #5935 - BNBU Online Judge System

编号	题目	状态	分数	总时间	内存	代码 / 答案文件	提交者	提交时间
#5935	#1062. 序列分段	Wrong Answer	5	2903 ms	9720 K	C++ 17 / 4.0 K	lly9981	2024-08-17 17:47:24

显示原始代码

#include <bits/stdc++.h>
using namespace std;
#define FastIO                   \

    ios::sync_with_stdio(false); \
    cin.tie(0), cout.tie(0);
#define endl "\n"

#define ll long long

// #define int long long
using i64 = int64_t;
using i128 = __int128;
const int maxN = 2e5 + 10;
const int MOD = 1e9 + 7;
int a[maxN];
int tr[maxN << 2], pos[maxN << 2];    //,lz[maxN<<2];
int tr1[maxN << 2], pos1[maxN << 2];  //,lz[maxN<<2];

void push_up(int id) {
    if (tr[2 * id] >= tr[2 * id + 1])
        tr[id] = tr[2 * id], pos[id] = pos[2 * id];
    else
        tr[id] = tr[2 * id + 1], pos[id] = pos[2 * id + 1];

    if (tr1[2 * id] <= tr1[2 * id + 1])
        tr1[id] = tr1[2 * id], pos1[id] = pos1[2 * id];
    else
        tr1[id] = tr1[2 * id + 1], pos1[id] = pos1[2 * id + 1];
}

void build(int id, int l, int r) {
    if (l == r) {
        tr[id] = a[l];
        pos[id] = l;
        tr1[id] = a[l];
        pos1[id] = l;
        return;
    }
    int mid = l + r >> 1;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);
    push_up(id);
}

void update(int id, int l, int r, int x, int v) {
    if (l == r) {
        tr[id] = v;
        pos[id] = x;
        tr1[id] = v;
        pos1[id] = x;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        update(2 * id, l, mid, x, v);
    else
        update(2 * id + 1, mid + 1, r, x, v);
    push_up(id);
}

pair<int, int> query(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return { tr[id], pos[id] };
    }
    int mid = l + r >> 1;
    pair<int, int> res = { INT_MIN, 0 }, cur;
    if (x <= mid) {
        cur = query(2 * id, l, mid, x, y);
        if (cur.first > res.first)
            swap(res, cur);
    }
    if (y > mid) {
        cur = query(2 * id + 1, mid + 1, r, x, y);
        if (cur.first > res.first)
            swap(res, cur);
    }
    return res;
}
pair<int, int> query1(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return { tr1[id], pos1[id] };
    }
    int mid = l + r >> 1;
    pair<int, int> res = { INT_MAX, 0 }, cur;
    if (x <= mid) {
        cur = query1(2 * id, l, mid, x, y);
        if (cur.first < res.first)
            swap(res, cur);
    }
    if (y > mid) {
        cur = query1(2 * id + 1, mid + 1, r, x, y);
        if (cur.first < res.first)
            swap(res, cur);
    }
    return res;
}
int query2(int id, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return tr[id];
    }
    int mid = l + r >> 1;
    int res = INT_MIN;
    if (x <= mid) {
        res = max(res, query2(2 * id, l, mid, x, y));
    }
    if (y > mid) {
        res = max(res, query2(2 * id + 1, mid + 1, r, x, y));
    }
    return res;
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            a[x] = y;
            update(1, 1, n, x, a[x]);
        }
        if (op == 2) {
            auto p = query(1, 1, n, x, y);
            int val = p.first, pos = p.second;

            int ans = a[x] + a[pos] + a[y];
            if (y - pos >= 2) {
                auto p1 = query(1, 1, n, pos + 1, y);
                int val1 = p1.first, pos1 = p1.second;
                if (pos1 + 1 <= n)
                    ans = min(ans, a[pos] + a[pos1] + a[n]);
                if (pos1 - 1 > pos)
                    ans = min(ans, a[pos] + a[pos1] + a[pos1 - 1]);
            }
            if (pos - x >= 2) {
                auto p1 = query(1, 1, n, x, pos - 1);
                int val1 = p1.first, pos1 = p1.second;
                if (pos1 + 1 < pos)
                    ans = min(ans, a[pos] + a[pos1] + a[n]);
                if (pos1 - 1 >= 1)
                    ans = min(ans, a[pos] + a[pos1] + a[pos1 - 1]);
            }
            auto p1 = query1(1, 1, n, x, y);
            val = p1.first, pos = p1.second;
            if (pos != x && pos != y) {
                // cout << pos << endl;
                // cout << pos + 1 << ' ' << y << endl;
                // cout << query2(1,1,n,x,pos - 1)<< endl;
                ans = min(ans, query2(1, 1, n, x, pos - 1) + val + query2(1, 1, n, pos + 1, y));
            }
            cout << ans << endl;
        }
    }
}

signed main() {
    FastIO int t = 1;
    // cin>>t;
    while (t--) solve();
    return 0;
}

子任务 #1

Wrong Answer

得分：5

测试点 #1

Accepted

得分：100

用时：3 ms

内存：412 KiB

输入文件（division1.in）

10 10
83983694 52500837 15295621 24900156 13874953 89464953 97841945 25988403 86558488 17513412 
1 2
<92 bytes omitted>

答案文件（division1.out）

用户输出

系统信息

Exited with return code 0

测试点 #2

Wrong Answer

得分：0

用时：3 ms

内存：376 KiB

输入文件（division2.in）

10 10
256719 90199811 42265012 11380538 54433648 51901463 11165841 95347781 655803 43565496 
1 7 162
<82 bytes omitted>

答案文件（division2.out）

用户输出

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #3

Wrong Answer

得分：0

用时：3 ms

内存：388 KiB

输入文件（division3.in）

50 50
37877166 97438616 8785140 36424982 41472406 37437062 42147344 6903643 99918080 64244254 224186
<833 bytes omitted>

答案文件（division3.out）

175126526
182416621
123929139
136390428
111686261
135000727
178582686
151152777
128867569
159624476

<217 bytes omitted>

用户输出

188108842
182416621
123929139
136390428
136045013
135000727
178582686
144420315
128867569
182024817
170772968
121975383
18106299
<192 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #4

Wrong Answer

得分：0

用时：3 ms

内存：364 KiB

输入文件（division4.in）

50 50
89515357 5362450 70771899 86655209 123810 77110827 32772085 89399383 97067460 51133699 1575426
<878 bytes omitted>

答案文件（division4.out）

143728001
184766382
118642263
132785528
133012072
117730520
114634231
109717372
113190366
159371760

<159 bytes omitted>

用户输出

143728001
184766382
118642263
132785528
133012072
143435099
114634231
145590387
164211961
189791671
200507600
166777293
15083177
<131 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #5

Wrong Answer

得分：0

用时：3 ms

内存：524 KiB

输入文件（division5.in）

50 50
34306222 28477878 88327443 17808768 44031451 83463345 46051881 16307296 64955639 16584648 7572
<912 bytes omitted>

答案文件（division5.out）

128017780
107843137
163474075
150839721
222223824
174133334
128339106
120708260
172262529
133879220

<99 bytes omitted>

用户输出

128017780
107843137
163474075
164125178
222223824
174133334
178916921
150429320
172262529
133879220
139217175
150429320
12974343
<71 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #6

Wrong Answer

得分：0

用时：3 ms

内存：504 KiB

输入文件（division6.in）

500 500
3510892 51945480 89371799 26009258 53268725 22305224 99132650 31211162 27533556 77773367 329
<10334 bytes omitted>

答案文件（division6.out）

127396451
200754234
138742620
227055220
144826305
132638681
144326288
169186864
178708671
196656641

<2528 bytes omitted>

用户输出

127396451
200754234
143495855
227055220
186734559
164654337
154364349
169186864
198186133
198174521
199611346
196522708
19836187
<2500 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #7

Wrong Answer

得分：0

用时：3 ms

内存：372 KiB

输入文件（division7.in）

500 500
24968281 95327119 41639604 10257696 8674927 58543160 16075497 5472824 36367619 76579359 1842
<10431 bytes omitted>

答案文件（division7.out）

148711506
163324978
156587411
110397943
164043582
180720951
184210441
133084992
170187886
185122095

<2410 bytes omitted>

用户输出

148711506
194452469
197604794
126676147
199364079
199104173
197897708
133084992
173545255
185122095
176633938
153794210
11658667
<2382 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #8

Wrong Answer

得分：0

用时：3 ms

内存：404 KiB

输入文件（division8.in）

500 500
3597506 84605791 83375205 79676577 29632308 69318479 51714861 79835235 92030255 62752405 456
<10405 bytes omitted>

答案文件（division8.out）

182298655
128589710
206262479
173023112
150681941
166327578
198114060
186412448
152332825
189509026

<2470 bytes omitted>

用户输出

185877056
150982554
210690550
173023112
150681941
180059413
200591936
195973004
159258360
190707977
192088311
196079127
19525356
<2442 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #9

Wrong Answer

得分：0

用时：3 ms

内存：512 KiB

输入文件（division9.in）

500 500
12394042 62272686 71442288 59088838 45673656 13682487 23209803 51659909 1517940 43412745 310
<10478 bytes omitted>

答案文件（division9.out）

139053322
128089723
190727864
174768849
136685743
182866655
200994849
120730780
119914018
139476532

<2299 bytes omitted>

用户输出

196878111
188530017
197562704
185386329
136685743
182866655
199738810
120730780
119914018
139476532
201333161
133985622
19413746
<2271 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #10

Wrong Answer

得分：0

用时：9 ms

内存：668 KiB

输入文件（division10.in）

5000 5000
6324701 69381184 40116200 58563577 49300296 77349548 19710883 51368622 15122894 87207955 1
<112392 bytes omitted>

答案文件（division10.out）

150381635
152047653
150592359
152808102
142078222
164185955
130216454
155210957
127320497
165596402

<25148 bytes omitted>

用户输出

150381635
152047653
150592359
152808102
142078222
164185955
130216454
155210957
127320497
165596402
138435651
154967293
17531892
<25120 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #11

Wrong Answer

得分：0

用时：9 ms

内存：644 KiB

输入文件（division11.in）

5000 5000
41638099 98619676 35040119 75006429 24101682 87910455 15475042 55744892 42741343 93395553 
<112363 bytes omitted>

答案文件（division11.out）

177128487
113086802
173646688
126890680
149739795
153954474
168979054
122481558
106861457
178639910

<25080 bytes omitted>

用户输出

195748949
113086802
184246813
126890680
149739795
153954474
192598708
122481558
106861457
186089541
131568434
165278975
11672049
<25052 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #12

Wrong Answer

得分：0

用时：8 ms

内存：612 KiB

输入文件（division12.in）

5000 5000
93995850 98551473 91188810 92943641 88292375 61613702 27459651 43979621 23482116 23136319 
<112757 bytes omitted>

答案文件（division12.out）

194225209
122835310
106454063
184052461
183034818
123920990
186605541
185030568
108695922
176688666

<24170 bytes omitted>

用户输出

199123299
156454468
108513764
199597548
199908392
123920990
189575184
199826766
157277790
187634544
194114944
199574344
19391437
<24142 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #13

Wrong Answer

得分：0

用时：10 ms

内存：636 KiB

输入文件（division13.in）

5000 5000
20479416 46096930 8292411 51105801 60715408 83955494 46449142 63059232 93106812 7200969 67
<112471 bytes omitted>

答案文件（division13.out）

183318362
119321258
143560648
194211999
179525259
177888813
139907457
185123124
135974207
184279223

<24937 bytes omitted>

用户输出

199998431
119321258
143560648
199564429
198495373
182285534
159679772
199998431
135974207
198694474
199933561
199093427
11643762
<24909 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #14

Wrong Answer

得分：0

用时：408 ms

内存：9404 KiB

输入文件（division14.in）

200000 200000
20336157 68372826 28644432 90856079 28793382 53819900 37847799 61890242 25926169 55808
<4999032 bytes omitted>

答案文件（division14.out）

157824658
156685676
161351865
189265647
138490825
177656856
167814307
151251895
151899605
152295574

<1001480 bytes omitted>

用户输出

157824658
156685676
161351865
189265647
138490825
177656856
175589438
151251895
151899605
173784069
135287141
144554371
14151300
<1001452 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #15

Wrong Answer

得分：0

用时：401 ms

内存：9440 KiB

输入文件（division15.in）

200000 200000
46962374 79383651 8286431 84414700 24997921 97632442 49271439 97026253 24603486 889502
<4999023 bytes omitted>

答案文件（division15.out）

145588131
128878062
152213039
122050708
113768138
169150615
171646168
166769309
171637010
143945500

<1002239 bytes omitted>

用户输出

145588131
128878062
152213039
122050708
113768138
172029376
171646168
166769309
179776317
143945500
129138862
122488964
12892606
<1002211 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #16

Wrong Answer

得分：0

用时：413 ms

内存：9384 KiB

输入文件（division16.in）

200000 200000
35414731 60678011 19273638 86352434 13976943 68967398 22620797 91125434 32877069 79676
<4999604 bytes omitted>

答案文件（division16.out）

140446353
127007397
145175596
153765790
131415461
136759223
163701274
111967464
160049635
148771459

<998718 bytes omitted>

用户输出

140446353
127007397
145175596
153765790
131415461
136759223
185568754
111967464
160049635
148771459
162913484
129919872
17136309
<998690 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #17

Wrong Answer

得分：0

用时：405 ms

内存：9468 KiB

输入文件（division17.in）

200000 200000
10904107 1181448 57344996 83661430 66824020 41214919 76514821 80096068 36027402 313858
<5000025 bytes omitted>

答案文件（division17.out）

156690952
159805546
119929439
164127255
190539719
164645764
166166031
141260257
135218754
199794072

<999919 bytes omitted>

用户输出

199951159
185061052
119929439
191808941
199980247
199995366
166166031
199995366
148565253
199997745
197822356
199988726
19999774
<999891 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #18

Wrong Answer

得分：0

用时：396 ms

内存：9532 KiB

输入文件（division18.in）

200000 200000
32655798 7964227 71044432 68690636 52582609 34489752 9374107 31768820 85754259 1942424
<4999057 bytes omitted>

答案文件（division18.out）

189414001
181063231
149128886
143938903
196912372
143258239
130594392
169126390
168287414
129141626

<1003810 bytes omitted>

用户输出

199993874
199970926
172594592
199997306
199994909
153728640
163823549
199969997
199995795
193814402
199980547
199971240
19069087
<1003782 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #19

Wrong Answer

得分：0

用时：413 ms

内存：9476 KiB

输入文件（division19.in）

200000 200000
51842175 82436523 77857980 36701667 70669233 70229173 35463762 6433395 46973470 322041
<5000053 bytes omitted>

答案文件（division19.out）

116786458
159547697
171618976
162512422
186306871
148680429
123038081
138520298
167189888
198733032

<999928 bytes omitted>

用户输出

174983822
163647688
199985061
199995239
199984642
148680429
142175446
138520298
197837368
199943770
199994953
196316278
19945677
<999900 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0

测试点 #20

Wrong Answer

得分：0

用时：404 ms

内存：9720 KiB

输入文件（division20.in）

200000 200000
99882522 1967005 52617374 44442885 89753615 49726115 17300918 4991072 93995038 3704729
<5000809 bytes omitted>

答案文件（division20.out）

193628016
131748702
179303740
140380995
163749667
117517045
136245762
128673075
161949913
134434225

<997078 bytes omitted>

用户输出

199998261
198262190
179303740
193411072
189977485
117517045
136245762
158172259
168092527
183536423
150953449
199970151
13108861
<997051 bytes omitted>

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0