QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #194798 | #3857. Single-track railway | realcomplex0# | AC ✓ | 955ms | 24112kb | C++14 | 2.6kb | 2023-09-30 22:34:25 | 2023-09-30 22:34:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)2e5 + 10;
ll d[N];
struct Node{
ll d1;
ll d2;
ll lazy1;
ll lazy2;
};
Node T[N * 4];
void push(int node, int cl, int cr){
T[node].d1 += T[node].lazy1;
T[node].d2 += T[node].lazy2;
if(cl != cr){
T[node * 2].lazy1 += T[node].lazy1;
T[node * 2 + 1].lazy1 += T[node].lazy1;
T[node * 2].lazy2 += T[node].lazy2;
T[node * 2 + 1].lazy2 += T[node].lazy2;
}
T[node].lazy1 = T[node].lazy2 = 0;
}
void update(int node, int cl, int cr, int tl, int tr, int typ, ll w){
push(node, cl, cr);
if(cr < tl || cl > tr) return;
if(cl >= tl && cr <= tr){
if(typ == 0) T[node].lazy1 = w;
else T[node].lazy2 = w;
push(node, cl, cr);
return;
}
int mid = (cl + cr) / 2;
update(node * 2, cl, mid, tl, tr, typ, w);
update(node * 2 + 1, mid + 1, cr, tl, tr, typ, w);
}
pii get(int node, int cl, int cr, int id){
if(cl == cr){
return mp(T[node].d1, T[node].d2);
}
int mid = (cl + cr) / 2;
push(node * 2 + 1, mid + 1, cr);
push(node * 2, cl, mid);
if(mid >= id)
return get(node * 2, cl, mid, id);
else
return get(node * 2 + 1, mid + 1, cr, id);
}
int n;
ll diff(ll x){
return max(x,-x);
}
ll calc(){
int l = 1;
int r = n - 1;
while(l < r){
int mid = (l + r) / 2;
pii ff = get(1, 1, n, mid + 1);
if(ff.fi >= ff.se) r = mid;
else l = mid + 1;
}
// l, l + 1
pii A = get(1, 1, n, l);
pii B = get(1, 1, n, l + 1);
if(A.fi == A.se || B.fi == B.se) return 0ll;
ll lf = A.fi;
ll rf = B.se;
if(lf > rf) swap(lf, rf);
return diff(rf - (lf + d[l]));
}
int main(){
fastIO;
//freopen("in.txt", "r", stdin);
cin >> n;
for(int i = 1; i <= n - 1; i ++ ){
cin >> d[i];
update(1, 1, n, i + 1, n, 0, d[i]);
update(1, 1, n, 1, i, 1, d[i]);
}
cout << calc() << "\n";
int q;
cin >> q;
int id;
ll dd;
for(int iq = 1; iq <= q; iq ++ ){
cin >> id >> dd;
update(1, 1, n, id + 1, n, 0, -d[id]);
update(1, 1, n, 1, id, 1, -d[id]);
d[id] = dd;
update(1, 1, n, id + 1, n, 0, d[id]);
update(1, 1, n, 1, id, 1, d[id]);
cout << calc() << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5700kb
input:
2 39 7 1 20 1 70 1 56 1 37 1 37 1 37 1 91
output:
39 20 70 56 37 37 37 91
result:
ok 8 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
3 8 41 0
output:
33
result:
ok single line: '33'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5672kb
input:
30 86 100 80 30 23 17 90 98 20 3 43 31 49 14 14 47 13 44 7 30 50 29 67 68 56 69 28 61 81 10 21 23 7 99 16 70 3 50 4 17 26 42 7 37 10 43 26 83 13 96
output:
8 19 28 5 3 10 11 17 5 18 1
result:
ok 11 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
150 7 76 71 86 28 49 57 12 30 79 91 52 27 49 5 30 2 27 31 49 69 73 57 53 57 6 94 35 30 16 51 71 50 82 34 31 65 2 63 91 20 89 92 11 39 88 36 40 26 16 46 20 87 89 74 43 99 39 55 60 82 27 52 83 20 95 22 16 1 51 64 79 53 59 88 13 94 64 73 47 67 77 24 9 59 49 70 77 49 3 62 24 16 70 10 95 78 16 75 64 44 4...
output:
1 18 44 63 61 60 23 41 35 1 18 21 45 56 85 79 70 58 91 69 81 77 55 49 7 20 5 1 49 67 84 84 69 67 88 25 44 78 69 30 32 38 15 77 66 37 34 5 44 20 28 57 18 80 9 8 7 10 79 10 85 81 20 11 8 15 80 64 83 83 58 61 18 33 48 5 6 29 69 12 51 19 6 19 37 26 4 16 74 40 73 71 74 67 56 52 35 77 66 76 34 37 85 57 57...
result:
ok 501 lines
Test #5:
score: 0
Accepted
time: 7ms
memory: 6252kb
input:
5000 11 95 41 4 70 9 85 27 53 63 58 34 55 56 38 100 51 37 9 30 40 79 58 44 9 62 30 89 34 28 48 7 39 41 37 15 34 3 76 8 13 28 92 25 51 97 68 29 53 29 48 59 85 70 84 71 59 89 32 77 25 1 16 5 75 95 48 98 41 25 17 65 11 12 16 48 11 26 67 82 40 61 41 7 9 11 30 15 70 62 72 82 1 85 15 60 55 3 97 72 33 56 5...
output:
25 6 10 42 2 5 17 9 35 22 27 33 36 1 21 10 12 13 34 79 39 39 67 20 5 26 54 59 73 46 53 100 56 100 89 82 67 94 95 72 74 25 12 6 31 63 71 84 52 60 67 71 65 6 28 41 26 30 42 18 4 26 32 7 17 22 22 20 3 14 7 20 30 37 41 27 41 85 36 85 76 62 34 50 41 27 76 73 91 67 79 31 23 92 68 87 63 85 64 46 23 22 4 79...
result:
ok 4001 lines
Test #6:
score: 0
Accepted
time: 79ms
memory: 6724kb
input:
10000 62 38 17 45 76 67 23 23 77 13 62 7 85 90 67 66 68 62 80 6 89 4 64 88 38 38 55 75 17 24 7 25 12 98 75 27 39 55 25 45 98 4 82 57 48 46 22 62 89 37 98 94 61 45 80 11 84 28 44 30 96 24 65 46 58 66 25 83 96 35 65 41 99 60 10 79 94 33 6 64 52 95 72 85 90 82 41 75 68 36 5 23 67 79 5 94 43 31 4 60 56 ...
output:
23 24 34 28 14 66 52 12 29 28 64 58 7 0 6 20 28 27 26 36 68 54 43 13 55 5 1 16 2 31 10 5 7 1 19 73 68 57 69 65 34 40 39 68 7 11 8 0 17 6 3 20 23 29 18 8 70 22 21 20 31 23 67 17 20 7 35 63 52 61 55 66 13 12 53 66 27 85 52 22 3 30 22 8 6 23 80 40 4 4 20 76 87 87 18 43 61 13 23 35 49 21 40 50 17 60 29 ...
result:
ok 30001 lines
Test #7:
score: 0
Accepted
time: 248ms
memory: 10876kb
input:
50000 54 92 38 60 53 71 8 36 15 95 40 23 65 9 26 90 66 78 49 32 100 14 51 74 31 87 4 55 56 45 98 71 67 90 19 11 58 74 24 58 11 21 69 10 77 8 21 53 65 10 92 62 32 92 47 53 92 24 39 7 82 90 57 88 22 53 95 53 20 18 97 100 5 28 37 5 81 63 49 32 39 90 94 38 67 56 79 25 56 21 95 35 11 39 65 71 66 69 46 68...
output:
39 53 25 79 64 33 26 7 15 44 74 46 21 52 33 22 38 13 33 5 80 67 53 65 41 45 80 80 66 21 27 30 6 2 34 65 55 88 24 54 70 80 53 47 13 9 74 26 25 2 4 7 58 50 68 59 71 84 74 73 52 9 3 24 8 3 4 31 49 79 5 2 34 48 70 79 60 46 3 6 39 71 78 0 85 29 45 22 53 31 6 9 40 21 8 9 43 33 83 80 24 21 0 56 74 62 47 33...
result:
ok 70001 lines
Test #8:
score: 0
Accepted
time: 478ms
memory: 15164kb
input:
100000 64 84 86 63 34 72 80 67 19 76 61 36 10 33 21 8 48 83 52 30 12 56 40 54 7 42 43 9 9 51 92 56 13 23 96 8 89 7 42 83 37 38 33 66 56 53 13 17 32 48 60 24 8 19 56 36 54 81 88 75 28 18 19 62 96 69 10 49 22 17 51 21 81 24 65 7 49 65 99 19 5 50 5 81 29 9 26 27 8 86 57 24 12 33 21 36 81 93 97 62 1 43 ...
output:
28 8 24 69 27 7 49 9 5 14 2 47 37 19 6 48 53 77 60 46 4 33 86 56 49 20 40 26 88 77 46 69 72 47 76 25 34 58 43 51 53 45 51 63 66 2 67 45 26 32 35 29 29 52 27 20 33 44 25 18 65 65 3 8 69 46 39 48 63 21 22 30 90 25 84 54 48 47 26 43 82 60 71 71 29 27 12 22 31 3 36 49 84 64 3 28 40 68 76 30 24 44 81 89 ...
result:
ok 120001 lines
Test #9:
score: 0
Accepted
time: 665ms
memory: 21616kb
input:
160000 19 10 84 78 78 100 91 27 83 53 1 84 63 27 69 22 83 98 75 38 6 57 22 23 84 51 55 11 87 34 58 57 45 89 24 47 25 41 66 77 14 82 13 48 78 79 41 6 49 18 90 76 27 90 39 37 79 48 69 11 78 34 1 26 14 47 51 19 81 76 70 77 97 77 45 74 18 27 10 79 23 64 32 61 88 56 1 85 53 49 13 62 16 43 80 48 59 58 43 ...
output:
13 15 30 8 6 8 0 15 23 4 23 21 38 27 32 24 2 3 13 14 4 27 17 31 8 23 7 9 12 40 15 26 16 35 13 26 52 49 42 41 36 39 36 13 69 4 29 6 24 8 29 43 7 20 2 54 34 55 18 37 4 25 63 50 14 4 29 55 16 2 5 14 2 50 38 18 48 22 46 38 38 12 39 23 35 20 13 27 44 39 19 12 3 37 44 51 7 13 0 13 37 25 27 40 22 35 34 23 ...
result:
ok 150001 lines
Test #10:
score: 0
Accepted
time: 911ms
memory: 24044kb
input:
200000 8 34 100 26 32 83 90 49 78 76 31 64 23 43 92 94 92 50 82 21 34 38 43 4 22 89 76 55 27 70 77 59 26 4 83 44 21 10 64 8 50 19 92 99 22 19 42 52 86 79 67 73 3 13 30 11 75 80 76 19 24 59 79 25 22 93 1 78 93 70 53 80 27 13 18 28 76 86 57 86 46 10 7 72 46 43 53 22 77 4 14 35 37 4 3 9 38 79 10 8 93 3...
output:
42 33 34 2 16 25 43 3 19 19 10 2 30 23 36 46 6 2 25 13 6 9 13 30 46 31 63 51 65 2 67 55 82 34 19 34 43 19 42 43 60 36 12 19 27 46 33 52 60 67 29 55 63 6 32 24 35 43 17 48 25 23 33 12 46 30 37 38 51 28 40 33 29 46 67 31 92 99 88 47 7 19 72 0 18 70 37 34 30 2 17 19 53 55 50 39 26 18 46 45 18 6 3 0 7 2...
result:
ok 200001 lines
Test #11:
score: 0
Accepted
time: 924ms
memory: 24048kb
input:
200000 1000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
800002 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 800002 1 80000...
result:
ok 200001 lines
Test #12:
score: 0
Accepted
time: 900ms
memory: 24112kb
input:
200000 999996 7 4 6 3 2 1 6 6 1 10 7 5 5 2 9 6 4 7 3 1 2 5 7 1 7 7 5 10 3 1 9 7 9 8 8 7 1 5 7 8 1 3 4 3 2 2 2 10 1 2 8 6 6 8 4 6 2 7 3 8 5 1 6 7 10 4 3 3 10 10 4 6 8 3 2 3 4 10 3 3 5 4 1 8 2 10 1 4 5 5 3 10 2 5 7 1 3 5 10 8 9 1 6 8 3 9 3 8 8 2 9 2 4 9 5 7 5 1 5 7 6 5 7 3 7 7 2 9 7 9 5 10 10 5 2 6 10...
output:
1 899643 3 1 4 899634 1 5 1 899640 1 7 1 899639 3 7 3 899638 5 6 5 899647 1 6 3 899640 0 7 2 899640 2 1 0 899638 2 0 3 899643 4 2 5 899640 4 5 2 899638 2 3 3 899640 4 7 0 899640 2 3 4 899645 1 8 3 899639 4 8 0 899643 4 4 5 899644 2 5 1 899634 1 4 5 899644 3 5 1 899647 1 4 3 899640 4 0 4 899634 4 7 3...
result:
ok 200001 lines
Test #13:
score: 0
Accepted
time: 955ms
memory: 21924kb
input:
200000 317938 219927 155685 111489 565924 604299 621658 687792 227393 452425 613272 701003 712740 588319 229660 882320 302465 489853 300038 19286 299173 705819 212476 744039 59678 959435 329118 701295 977974 817966 654854 243464 187401 132055 737139 802038 835052 966075 159950 22148 348823 252056 39...
output:
602290 730793 676088 56201 402016 598334 595042 778368 432336 381848 739186 580081 346934 700485 26164 485196 416174 335923 395099 241899 218118 630573 468395 499200 510076 241935 375392 174881 726742 655764 324768 296 777343 566627 203423 4949 686589 372460 804437 604888 542902 26884 449687 451596 ...
result:
ok 200001 lines