QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#335804 | #4077. 뚫기 | tuanlinh123 | 0 | 2ms | 4084kb | C++20 | 3.6kb | 2024-02-23 23:39:59 | 2024-02-23 23:39:59 |
answer
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const ll inf=1e18;
struct SegTree
{
struct Node
{
ll lzs=0;
pll Min={0, 0}, lzm={inf, 0};
Node(ll type=0) {if (type) Min.fi=inf;}
Node operator + (const Node &o) const
{
Node ans;
ans.Min=min(Min, o.Min);
return ans;
}
void act(ll ad, pll mi)
{
Min.fi+=ad, Min=min(Min, mi);
lzs+=ad, lzm.fi+=ad, lzm=min(lzm, mi);
}
};
ll n;
vector <Node> St;
SegTree (ll n): n(n) {St.resize(n*4+1);}
void Move(ll i)
{
St[i*2].act(St[i].lzs, St[i].lzm);
St[i*2+1].act(St[i].lzs, St[i].lzm);
St[i].lzs=0, St[i].lzm={inf, 0};
}
void update(ll i, ll Start, ll End, ll l, ll r, ll ad, pll mi)
{
if (Start>r || End<l) return;
if (Start>=l && End<=r) {St[i].act(ad, mi); return;}
ll mid=(Start+End)/2; Move(i);
if (l<=mid) update(i*2, Start, mid, l, r, ad, mi);
if (r>=mid+1) update(i*2+1, mid+1, End, l, r, ad, mi);
St[i]=St[i*2]+St[i*2+1];
}
void update(ll l, ll r, ll ad, pll mi) {update(1, 1, n, l, r, ad, mi);}
Node query(ll i, ll Start, ll End, ll l, ll r)
{
if (Start>r || End<l) return Node(1);
if (Start>=l && End<=r) return St[i];
ll mid=(Start+End)/2; Move(i);
if (l>mid) return query(i*2+1, mid+1, End, l, r);
if (r<mid+1) return query(i*2, Start, mid, l, r);
return query(i*2, Start, mid, l, r)+query(i*2+1, mid+1, End, l, r);
}
Node query(ll l, ll r) {return query(1, 1, n, l, r);}
};
ll n, m, l[10005], r[10005];
void init(int N, int M, vector <int> L, vector <int> R)
{
n=N, m=M;
for (ll i=0; i<n; i++)
l[i]=L[i], r[i]=R[i];
//compress numbers
{
vector <ll> num; num.pb(0), num.pb(m-1);
for (ll i=0; i<n; i++)
num.pb(l[i]), num.pb(r[i]);
sort(num.begin(), num.end());
num.resize(unique(num.begin(), num.end())-num.begin());
for (ll i=0; i<n; i++)
{
l[i]=lower_bound(num.begin(), num.end(), l[i])-num.begin()+1;
r[i]=lower_bound(num.begin(), num.end(), r[i])-num.begin()+1;
}
m=num.size();
}
auto Try=[&](ll A, ll B)
{
SegTree S(m);
for (ll i=0; i<n; i++)
{
S.update(l[i], r[i], B, {inf, 0});
SegTree::Node best=S.query(1, m);
S.update(1, m, 0, {best.Min.fi+A, best.Min.se+1});
}
ll cost, a, b;
tie(cost, a)=S.query(1, m).Min, b=(cost-a*A)/B;
return mp(a, b);
};
}
ll minimize(int A, int B)
{
SegTree S(m);
for (ll i=0; i<n; i++)
{
S.update(l[i], r[i], B, {inf, 0});
SegTree::Node best=S.query(1, m);
S.update(1, m, 0, {best.Min.fi+A, best.Min.se+1});
}
return S.query(1, m).Min.fi;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// ll n, m, q; cin >> n >> m >> q;
// int l[n], r[n];
// for (ll i=0; i<n; i++)
// cin >> l[i] >> r[i];
// init(n, m, l, r);
// for (ll i=0; i<q; i++)
// {
// ll A, B; cin >> A >> B;
// cout << minimize(A, B) << "\n";
// }
// }
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 0ms
memory: 3652kb
input:
6 2 1 1 1 0 1 0 0 0 1 1 1 0 1 724642704 32998300
output:
131993200
result:
ok single line: '131993200'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
10 3 1 1 2 1 2 0 2 1 2 2 2 0 2 1 1 0 2 0 1 1 2 686137157 255736273
output:
1022945092
result:
ok single line: '1022945092'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
50 5 1 0 1 4 4 3 4 1 4 0 3 1 4 1 3 0 4 0 0 0 3 0 1 0 3 0 0 2 3 0 0 3 4 1 1 2 2 0 1 0 1 0 4 1 4 3 4 0 1 0 4 2 2 0 3 0 3 0 4 0 3 0 4 2 4 0 0 4 4 3 3 1 4 2 3 0 2 0 1 0 3 2 3 3 3 2 3 2 4 2 2 0 2 1 2 0 4 1 3 2 4 404445464 361978179
output:
6196096328
result:
ok single line: '6196096328'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
121 7 1 2 5 5 6 1 6 0 6 4 5 1 6 2 4 2 4 0 6 2 6 1 5 3 4 0 4 1 6 0 2 0 5 2 6 1 6 1 2 1 4 0 6 1 5 0 5 0 6 0 6 0 6 1 4 0 4 3 5 1 6 0 0 0 5 1 3 0 6 0 3 1 3 1 2 2 3 0 5 1 4 2 4 0 5 0 0 1 3 1 6 0 2 1 6 2 5 2 4 0 6 1 2 2 4 3 4 0 5 0 6 0 6 1 6 0 6 0 4 2 6 0 1 0 2 0 3 0 5 3 6 2 4 4 4 1 6 5 5 0 4 0 5 0 0 2 3 ...
output:
16848723090
result:
ok single line: '16848723090'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
243 9 1 0 7 1 7 0 3 3 7 1 8 5 6 4 6 3 5 5 6 0 6 0 8 1 8 7 8 4 8 1 8 0 5 3 3 5 8 5 7 8 8 3 6 0 6 4 4 1 3 0 7 2 5 0 2 6 6 4 7 1 3 0 8 1 4 0 8 2 8 6 8 5 8 1 8 0 8 7 8 3 3 3 4 0 8 6 8 0 4 2 8 0 8 1 7 0 6 4 4 1 8 6 8 0 7 4 8 0 8 1 5 4 7 0 8 3 3 1 1 5 8 1 4 5 7 3 4 1 7 1 8 1 8 6 8 0 4 0 8 2 8 3 7 2 8 0 3 ...
output:
27719095584
result:
ok single line: '27719095584'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
1000 102 1 46 74 33 80 4 84 22 96 1 100 10 36 35 68 0 65 4 26 26 93 25 90 0 79 14 101 24 57 4 53 37 60 4 77 32 97 44 70 29 65 44 99 2 49 0 86 69 76 3 57 1 93 16 83 38 60 1 86 1 40 19 97 28 94 4 45 16 72 23 94 26 89 20 60 29 32 21 39 14 83 26 74 24 77 15 88 72 93 12 90 1 81 27 60 15 90 36 78 18 39 12...
output:
23789206007
result:
ok single line: '23789206007'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
2000 123 1 48 81 27 95 16 109 19 106 26 115 4 116 66 83 2 111 39 118 15 47 21 122 1 120 78 101 35 120 55 95 36 59 75 75 42 64 71 105 11 121 31 122 30 112 93 116 1 61 77 84 26 90 28 109 14 116 9 118 80 91 8 101 13 113 29 51 2 118 5 77 23 93 25 108 3 120 8 120 22 64 36 65 7 83 7 115 14 93 8 50 7 116 5...
output:
40092503040
result:
ok single line: '40092503040'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3856kb
input:
3000 143 1 0 142 28 140 36 139 27 48 1 137 21 142 35 103 40 91 55 82 2 135 27 123 42 58 38 126 105 106 43 65 13 103 78 99 71 102 21 106 94 127 31 40 14 131 94 120 1 117 5 128 48 120 27 135 31 107 49 107 2 132 89 102 22 123 23 139 76 137 125 136 80 122 12 127 17 91 84 136 82 139 45 131 38 85 9 142 24...
output:
53183710390
result:
ok single line: '53183710390'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
3000 123 1 38 120 3 97 6 57 11 11 29 76 39 115 69 89 57 122 11 122 43 66 46 104 6 43 4 119 8 59 28 107 73 102 18 119 70 108 62 95 4 115 19 79 29 91 2 40 114 120 67 83 37 46 14 110 4 70 2 35 35 120 21 28 20 111 4 121 10 103 7 122 36 105 21 28 15 26 54 72 65 113 24 118 58 115 49 115 13 112 105 120 0 1...
output:
9990597533
result:
ok single line: '9990597533'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3860kb
input:
3000 102 1 94 95 51 101 91 99 9 92 8 80 2 60 45 57 1 96 40 83 8 8 15 87 10 98 44 89 40 96 13 62 4 67 6 35 0 101 36 95 15 53 56 86 55 88 38 74 11 50 0 61 0 93 32 69 7 60 32 82 9 98 7 97 18 100 70 91 26 80 27 101 21 69 0 101 43 49 45 97 17 73 1 12 0 36 40 86 44 92 57 68 15 87 57 68 54 75 66 101 10 88 ...
output:
69226624268
result:
ok single line: '69226624268'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
3000 6 1 4 4 5 5 2 2 0 5 3 3 0 5 0 4 1 4 0 2 0 4 1 5 1 5 0 3 4 5 2 3 1 5 1 3 3 5 0 3 3 3 3 5 1 3 2 2 1 5 0 1 3 4 2 4 0 0 4 4 0 2 1 4 3 4 1 3 0 1 0 1 0 0 2 4 0 2 0 4 2 5 0 5 0 4 0 1 0 3 1 5 2 4 2 4 0 5 2 5 3 4 0 5 1 5 4 5 2 4 1 1 1 3 0 5 0 4 0 3 5 5 1 5 0 2 1 5 2 5 0 5 0 3 2 3 3 4 4 4 2 3 2 5 0 1 4 5...
output:
282532939566
result:
ok single line: '282532939566'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3828kb
input:
3000 7 1 2 6 1 6 1 2 5 6 1 4 2 6 2 6 1 1 2 6 2 4 1 3 1 3 2 6 0 6 3 4 1 2 1 3 0 5 0 0 0 0 0 3 3 6 0 4 4 6 1 1 0 0 2 4 0 5 3 6 2 4 2 4 1 4 2 5 4 5 2 4 2 5 0 6 2 6 4 5 2 3 0 5 4 4 3 6 1 6 5 5 1 6 2 4 2 4 0 6 1 6 3 4 0 5 2 6 0 6 1 6 2 4 0 0 0 4 2 5 5 6 4 5 4 5 0 1 3 6 1 6 0 6 0 5 4 5 1 2 0 3 1 2 0 6 2 5...
output:
71432089700
result:
ok single line: '71432089700'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
3000 8 1 3 5 2 4 1 7 3 3 0 4 3 4 2 4 1 3 4 5 0 0 1 4 2 2 2 6 1 7 1 7 0 7 0 2 0 6 1 7 4 6 0 2 0 7 0 2 6 7 0 7 1 5 1 7 0 6 0 7 4 7 0 7 5 6 1 7 1 2 1 3 2 6 0 3 1 5 2 7 1 7 2 3 0 7 2 5 3 7 2 7 7 7 2 5 2 4 0 6 1 5 0 1 0 5 0 7 6 6 1 4 3 6 0 6 3 4 1 5 6 7 0 7 1 5 4 7 1 3 7 7 1 7 0 4 1 7 1 7 1 5 3 7 0 7 1 7...
output:
89022157300
result:
ok single line: '89022157300'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4084kb
input:
3000 9 1 1 8 0 3 1 7 3 7 2 7 0 8 1 8 3 8 0 8 2 3 2 7 1 7 0 5 0 8 3 7 1 5 0 8 4 4 1 7 6 6 5 6 3 4 1 4 1 7 0 8 0 6 5 8 0 0 0 7 1 3 1 7 2 5 1 4 1 7 4 7 0 8 0 8 1 8 0 7 4 8 3 8 0 8 0 8 0 6 0 8 2 3 2 8 2 7 2 7 0 8 2 3 0 3 3 7 2 5 0 8 1 4 1 4 2 6 3 6 3 6 6 8 2 7 3 8 1 3 0 8 2 6 3 7 2 6 0 4 1 8 4 8 0 6 1 8...
output:
379045773469
result:
ok single line: '379045773469'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
3000 10 1 3 6 6 9 3 9 0 8 0 4 0 8 4 9 4 5 0 4 6 6 0 8 2 6 4 7 0 6 0 8 4 4 3 8 0 4 9 9 5 9 0 8 1 4 0 3 0 8 3 5 0 4 3 9 4 7 0 9 0 8 1 3 2 4 0 7 4 5 0 6 7 8 0 4 9 9 0 8 1 6 5 5 3 9 1 8 1 8 0 2 2 2 3 9 2 3 4 4 1 7 3 7 2 3 2 9 6 9 1 4 1 7 1 2 6 6 4 5 2 7 4 9 4 6 2 6 1 5 7 8 1 4 3 7 6 6 4 9 9 9 3 7 1 2 0 ...
output:
331629106039
result:
ok single line: '331629106039'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3000 2934 1 1970 2832 110 2030 61 2595 313 2018 546 1871 1131 2583 216 2779 909 1996 864 1914 1011 1315 1365 2599 508 1996 955 2087 310 1272 1955 2337 781 1719 155 815 837 1681 25 2913 841 1953 376 2752 388 1124 1099 2382 1323 2198 851 2217 1459 2721 465 2160 312 2250 55 1080 180 339 764 2865 82 253...
output:
2426370144
result:
ok single line: '2426370144'
Test #17:
score: 0
Accepted
time: 2ms
memory: 3864kb
input:
2942 3000 1 425 2447 791 893 243 2737 447 1479 1447 2468 181 2810 1219 2995 2407 2628 296 1770 1535 1779 1338 2418 441 1346 1916 2767 740 2628 4 1462 230 2239 1755 1880 33 2815 283 2054 922 1731 1236 2809 513 2469 190 2711 1692 1850 31 2959 369 1998 246 2694 2524 2867 1076 2822 1204 2795 153 1294 28...
output:
3475348346
result:
ok single line: '3475348346'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3828kb
input:
3000 3000 1 1390 1947 533 1520 288 2002 824 1075 363 2519 1187 2858 532 2977 31 2120 1 2937 1545 2305 1125 2756 835 2017 2055 2309 1621 2143 1316 1826 244 2875 1299 2494 509 2480 1384 1735 23 2976 443 752 290 993 495 2557 484 2973 718 1717 20 2576 470 1167 25 2557 157 2901 360 2798 1488 1917 719 294...
output:
1096040253
result:
ok single line: '1096040253'
Test #19:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
3000 11 1 6 10 3 10 0 6 0 10 0 8 2 10 4 10 0 7 0 3 0 10 0 7 0 1 4 10 0 2 7 10 0 10 0 10 1 10 2 10 9 10 9 10 8 10 10 10 0 2 0 5 7 10 0 1 0 2 8 10 0 10 0 10 0 10 0 6 9 10 5 10 0 7 0 10 0 2 0 7 4 10 6 10 0 3 0 1 6 10 3 10 4 10 7 10 2 10 0 9 10 10 0 2 8 10 3 10 9 10 0 9 5 10 0 5 4 10 0 6 0 10 0 10 10 10...
output:
231189542188
result:
ok single line: '231189542188'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3856kb
input:
3000 12 1 1 11 0 9 3 11 0 10 0 0 1 11 0 11 0 1 0 0 0 6 4 11 2 11 0 0 8 11 2 11 0 5 0 11 0 5 0 9 0 9 3 11 10 11 0 1 6 11 0 6 6 11 0 2 0 3 11 11 6 11 3 11 7 11 5 11 5 11 0 9 6 11 0 0 0 10 0 1 0 2 2 11 6 11 0 1 1 11 10 11 3 11 0 4 7 11 0 1 0 0 0 9 5 11 5 11 8 11 0 9 0 1 6 11 1 11 9 11 9 11 0 0 7 11 0 5...
output:
149422997346
result:
ok single line: '149422997346'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4020kb
input:
3000 13 1 6 12 0 1 4 12 0 2 4 12 0 12 1 12 3 12 11 12 0 11 10 12 9 12 0 6 0 4 9 12 1 12 0 11 0 12 10 12 5 12 0 8 11 12 2 12 0 12 7 12 0 10 4 12 11 12 0 8 0 12 6 12 0 2 0 6 4 12 5 12 4 12 0 7 1 12 0 2 3 12 9 12 9 12 4 12 0 12 8 12 0 4 0 7 4 12 10 12 0 1 0 2 12 12 7 12 4 12 0 5 0 3 0 9 0 1 0 11 6 12 0...
output:
193191161451
result:
ok single line: '193191161451'
Test #22:
score: 0
Accepted
time: 2ms
memory: 3900kb
input:
3000 3000 1 0 557 0 987 0 1714 0 251 843 2999 0 1671 0 2445 910 2999 63 2999 2239 2999 0 1631 1817 2999 2745 2999 2477 2999 0 510 0 2631 0 1195 1028 2999 0 351 0 2953 2690 2999 0 703 937 2999 0 2489 2000 2999 0 2556 0 697 467 2999 255 2999 0 2438 2570 2999 777 2999 0 964 0 1963 1344 2999 0 1766 2199...
output:
210328057904
result:
ok single line: '210328057904'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3804kb
input:
3000 2983 1 0 133 2599 2982 2541 2982 0 389 0 2825 0 432 561 2982 2514 2982 0 1865 0 706 720 2982 3 2982 1648 2982 0 1731 1890 2982 1570 2982 0 937 1853 2982 0 1418 687 2982 0 799 1530 2982 1446 2982 2216 2982 0 2047 0 2530 0 2971 0 1736 1767 2982 0 1447 0 47 601 2982 0 1758 84 2982 0 2756 0 2116 0 ...
output:
571590929028
result:
ok single line: '571590929028'
Test #24:
score: 0
Accepted
time: 2ms
memory: 3908kb
input:
2984 3000 1 0 1161 1028 2999 0 2476 0 2636 0 1914 0 776 0 2136 248 2999 0 48 2645 2999 0 829 2998 2999 359 2999 0 1766 0 927 2847 2999 1471 2999 0 1945 188 2999 295 2999 1426 2999 1831 2999 697 2999 1280 2999 0 1876 735 2999 0 1413 2326 2999 0 2970 537 2999 1249 2999 1147 2999 0 1827 0 943 0 213 0 1...
output:
472133773188
result:
ok single line: '472133773188'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
300 3000 1 2218 2999 2936 2999 2708 2999 2281 2999 0 1722 0 1888 0 1064 0 704 1925 2999 0 1753 2426 2999 0 1862 0 1830 572 2999 0 2435 798 2999 95 2999 1193 2999 507 2999 0 1299 0 2105 0 508 2672 2999 1956 2999 1742 2999 0 2278 0 118 586 2999 1966 2999 0 1101 77 2999 2768 2999 1755 2999 0 81 0 1013 ...
output:
54180869583
result:
ok single line: '54180869583'
Test #26:
score: -7
Wrong Answer
time: 0ms
memory: 3700kb
input:
102 3000 1 0 689 840 2999 1957 2999 0 1676 0 415 2411 2999 2855 2999 2582 2999 0 2096 2287 2999 1961 2999 0 1601 2643 2999 1220 2999 820 2999 0 1470 802 2999 392 2999 0 1762 1064 2999 2595 2999 0 748 1501 2999 0 991 0 617 0 1021 0 1598 1753 2999 0 717 0 2553 1705 2999 0 646 0 106 109 2999 0 2738 284...
output:
2016258568
result:
wrong answer 1st lines differ - expected: '1972426860', found: '2016258568'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Time Limit Exceeded
Test #60:
score: 0
Time Limit Exceeded
input:
500 10 1000000 2 9 2 7 3 6 1 6 3 5 0 5 3 4 6 8 4 8 1 6 1 5 6 7 7 7 6 9 0 7 4 5 0 6 0 2 4 6 0 6 1 7 2 8 0 9 0 9 0 9 0 7 3 6 8 8 2 4 4 4 0 5 2 5 1 6 0 9 2 7 0 8 9 9 1 4 0 9 2 4 1 9 2 8 2 6 0 4 5 9 4 5 3 9 2 6 1 9 0 6 6 8 2 9 4 9 7 9 2 7 1 5 1 8 0 6 0 9 2 9 3 9 0 2 4 4 5 9 4 7 8 9 4 9 1 8 3 8 2 9 6 6 3...
output:
109125435050 79679504214 40397444309 33486843995 50549382350 8831039674 29373662236 35916635082 1627822212 83193326242 7021463069 18347246004 17908310304 40111838606 42807634739 83808922569 36682521996 87471336298 56912099994 74488880562 59044328919 71779759293 47086282044 46402519236 10235901992 55...
result:
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%