QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #793475 | #686. Bad Doctor | Sktn0089 | WA | 1987ms | 93288kb | C++14 | 2.5kb | 2024-11-29 20:22:50 | 2024-11-29 20:22:52 |
Judging History
answer
//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
namespace Initial {
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
template <class T>
void rd(T &x) {
char ch; bool f = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') f = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(f) x = -x;
}
void write(const ll x, const char str[] = "") {
if(x > 9) write(x / 10);
putchar(x % 10 + '0'), printf("%s", str);
}
const ll maxn = 1e6 + 10, inf = 1e18, L = 1e6; ll mod;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %mod;
a = 1ll * a * a %mod, b >>= 1;
} return s;
}
template <class T>
const ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
ll n, m, a[maxn], l[maxn], r[maxn], ans[maxn];
vector <ll> vec[maxn]; ll sum;
struct SGT {
ll cnt[maxn << 2], tag[maxn << 2];
void modify(ll p, ll l, ll r, ll ql, ll qr, ll v) {
if(ql <= l && r <= qr) {
tag[p] += v;
cnt[p] = tag[p]? r - l + 1 : cnt[p << 1] + cnt[p << 1|1];
return;
} ll mid = l + r >> 1;
if(ql <= mid) modify(p << 1, l, mid, ql, qr, v);
if(mid < qr) modify(p << 1|1, mid + 1, r, ql, qr, v);
cnt[p] = tag[p]? r - l + 1 : cnt[p << 1] + cnt[p << 1|1];
}
} tr;
int main() {
// freopen("ex_doctor3.in", "r", stdin);
// freopen("doctor.out", "w", stdout);
rd(n), rd(m);
for(ll i = 1; i <= m; i++) rd(a[i]);
for(ll i = 1; i <= n; i++) {
ll k; rd(l[i]), rd(r[i]), rd(k);
for(ll j = 1, x; j <= k; j++)
rd(x), vec[x].pb(i);
}
for(ll c = 1; c <= m; c++) {
for(ll i: vec[c])
tr.modify(1, 1, L, l[i], r[i], 1);
sum += tr.cnt[1] * a[c];
for(ll i: vec[c]) {
ll tmp = tr.cnt[1];
tr.modify(1, 1, L, l[i], r[i], -1);
ans[i] += (tmp - tr.cnt[1]) * a[c];
tr.modify(1, 1, L, l[i], r[i], 1);
}
for(ll i: vec[c])
tr.modify(1, 1, L, l[i], r[i], -1);
}
for(ll i = 1; i <= n; i++) write(sum - ans[i], " ");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 40640kb
input:
5 4 1000 100 10 1 3 4 2 2 3 4 8 3 1 2 4 6 7 2 3 4 8 9 2 1 4 2 6 3 1 2 3
output:
8766 7564 8756 7765 6646
result:
ok 5 number(s): "8766 7564 8756 7765 6646"
Test #2:
score: 0
Accepted
time: 0ms
memory: 28736kb
input:
1 1 1 1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 4ms
memory: 29040kb
input:
1 2 10 1 1 2 1 2
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 27284kb
input:
2 1 1 1 2 1 1 3 4 1 1
output:
2 2
result:
ok 2 number(s): "2 2"
Test #5:
score: 0
Accepted
time: 0ms
memory: 27624kb
input:
2 1 1 1 2 1 1 2 3 1 1
output:
2 2
result:
ok 2 number(s): "2 2"
Test #6:
score: 0
Accepted
time: 3ms
memory: 30420kb
input:
1 3 1000000 909090 700700 1 1000000 3 1 2 3
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 3ms
memory: 27836kb
input:
2 1 1000000 1 500000 1 1 500000 1000000 1 1
output:
500001000000 500000000000
result:
ok 2 number(s): "500001000000 500000000000"
Test #8:
score: 0
Accepted
time: 4ms
memory: 28488kb
input:
2 2 10 1 3 8 1 1 5 9 1 2
output:
5 60
result:
ok 2 number(s): "5 60"
Test #9:
score: 0
Accepted
time: 7ms
memory: 42688kb
input:
2 2 10 1 3 8 2 1 2 5 9 1 2
output:
5 66
result:
ok 2 number(s): "5 66"
Test #10:
score: 0
Accepted
time: 7ms
memory: 40620kb
input:
2 2 10 1 3 8 2 1 2 5 6 1 1
output:
20 66
result:
ok 2 number(s): "20 66"
Test #11:
score: 0
Accepted
time: 5ms
memory: 42732kb
input:
2 2 10 1 6 6 2 1 2 2 2 1 2
output:
1 11
result:
ok 2 number(s): "1 11"
Test #12:
score: 0
Accepted
time: 0ms
memory: 44764kb
input:
2 2 10 1 6 6 1 2 1 2 1 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 46820kb
input:
3 1 1 1 6 1 1 3 16 1 1 8 11 1 1
output:
14 10 16
result:
ok 3 number(s): "14 10 16"
Test #14:
score: 0
Accepted
time: 0ms
memory: 44724kb
input:
3 1 1 1 8 1 1 3 15 1 1 5 12 1 1
output:
13 12 15
result:
ok 3 number(s): "13 12 15"
Test #15:
score: 0
Accepted
time: 0ms
memory: 44724kb
input:
3 2 10 1 1 6 2 1 2 4 9 1 1 5 10 1 2
output:
66 70 96
result:
ok 3 number(s): "66 70 96"
Test #16:
score: 0
Accepted
time: 0ms
memory: 48824kb
input:
3 2 10 1 1 6 2 1 2 7 9 1 1 3 6 1 2
output:
34 66 96
result:
ok 3 number(s): "34 66 96"
Test #17:
score: 0
Accepted
time: 0ms
memory: 44732kb
input:
3 2 10 1 1 3 2 1 2 5 6 1 1 8 12 1 2
output:
25 38 53
result:
ok 3 number(s): "25 38 53"
Test #18:
score: 0
Accepted
time: 0ms
memory: 46820kb
input:
3 2 10 1 1 8 1 1 1 1 1 2 3 4 2 1 2
output:
23 82 81
result:
ok 3 number(s): "23 82 81"
Test #19:
score: 0
Accepted
time: 4ms
memory: 42676kb
input:
3 3 100 10 1 3 5 2 2 3 8 8 1 2 8 8 2 1 3
output:
111 134 43
result:
ok 3 number(s): "111 134 43"
Test #20:
score: 0
Accepted
time: 4ms
memory: 42716kb
input:
5 5 10000 1000 100 10 1 1 4 1 4 7 9 2 4 5 8 10 5 1 2 3 4 5 5 6 4 1 2 3 4 2 3 3 1 2 4
output:
77584 77593 44293 55384 55604
result:
ok 5 number(s): "77584 77593 44293 55384 55604"
Test #21:
score: 0
Accepted
time: 0ms
memory: 40640kb
input:
10 7 552910 150933 995175 215236 872242 381236 155576 2 9 2 1 3 5 8 4 1 3 4 7 13 20 2 2 4 17 19 4 1 2 3 6 16 19 4 3 4 5 7 6 10 4 1 2 6 7 16 16 4 1 4 5 7 6 12 3 3 4 7 14 16 4 2 3 6 7 12 18 4 1 2 3 5
output:
41574799 45848242 45207177 44522436 44880084 43005299 46219054 43056608 44764194 39372338
result:
ok 10 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 40676kb
input:
7 10 736484 818923 456465 12520 997843 981585 612726 181577 186139 168089 3 11 4 2 7 8 10 1 4 1 1 12 13 6 1 2 3 5 6 7 10 14 3 2 6 9 17 20 5 3 4 5 6 8 3 13 2 1 7 20 20 2 2 6
output:
40495012 47901499 46465851 44680094 39836092 44219079 48555544
result:
ok 7 numbers
Test #23:
score: 0
Accepted
time: 7ms
memory: 46748kb
input:
30 10 857308 953250 600059 683156 139561 641008 542233 928243 893627 191827 2 22 2 5 8 29 50 2 1 3 47 48 3 7 8 10 21 22 2 8 9 42 45 3 3 6 9 4 27 4 5 6 8 10 45 50 1 8 26 39 3 1 4 10 40 44 5 6 7 8 9 10 44 46 5 1 4 6 7 9 44 44 3 1 8 10 2 24 5 3 6 7 8 10 4 39 2 3 4 40 46 2 3 4 30 45 5 1 2 7 8 9 10 45 3 ...
output:
293838811 290066769 292754345 292051557 293838811 293646984 293838811 292879676 293005976 292402951 293838811 287917175 285973327 291106187 284902541 291127646 267465483 281328033 293838811 293699250 293838811 293838811 293315596 290979061 293838811 292514647 293838811 293838811 293838811 293838811
result:
ok 30 numbers
Test #24:
score: 0
Accepted
time: 3ms
memory: 44744kb
input:
10 30 391716 868283 902120 388402 981355 289714 570338 351001 196034 286794 661345 223544 480989 228068 668284 480867 671125 927397 983725 983858 967588 276597 257618 199614 61676 473411 45932 450727 45681 368382 11 26 7 1 13 14 15 16 19 27 15 16 4 13 14 29 30 19 46 4 6 21 22 30 37 38 6 9 10 18 20 2...
output:
123670461 171088996 119574830 165992964 169391754 153780399 165654628 148473523 166617345 168366240
result:
ok 10 numbers
Test #25:
score: 0
Accepted
time: 0ms
memory: 42688kb
input:
60 40 214784 374560 331541 383120 553085 21716 253180 156648 54233 898460 696585 177744 806924 494782 17110 123004 611634 437506 349347 472426 960396 841591 117777 2457 743805 923885 808421 626506 444686 822906 738699 897414 751402 715382 174480 428567 525859 418878 139239 73165 43 94 2 4 34 73 86 1...
output:
1286380648 1288526794 1287651782 1283846804 1287658154 1280320699 1254862714 1287023990 1288514509 1287558232 1274668519 1288526794 1285120582 1261510038 1287007714 1286808665 1217981437 1288526794 1287552121 1288526794 1282578830 1286766918 1287478927 1279195034 1284937138 1268832042 1288526794 127...
result:
ok 60 numbers
Test #26:
score: 0
Accepted
time: 6ms
memory: 42616kb
input:
40 60 432564 15941 218898 381405 944405 622234 901280 644715 561289 369329 730603 514677 977787 810908 656473 232857 767720 878754 732768 319462 580706 196541 515660 633761 862798 740252 717437 351747 274470 884642 524838 3384 279161 303717 166799 106145 290214 443696 285588 707603 248932 403905 578...
output:
1521415473 1507270535 1517038227 1514380823 1513870185 1492434944 1508816703 1474941708 1485455736 1505592494 1518157381 1451068000 1519494183 1471167676 1517031855 1514809221 1490573182 1516619035 1520254617 1511020126 1455246571 1495439950 1515754649 1484130967 1520939771 1492389078 1496487626 152...
result:
ok 40 numbers
Test #27:
score: 0
Accepted
time: 6ms
memory: 42740kb
input:
100 50 157617 567295 279380 280193 657430 128267 559638 21581 945026 885826 677464 647180 311530 842012 76705 816983 673923 87222 839864 280237 66121 894351 175723 666480 871548 487243 177099 42342 380062 144691 501870 873145 195318 221491 488364 683896 52175 255195 124899 758996 532153 367647 82898...
output:
3692970391 3688368381 3692970391 3686375123 3674040877 3692970391 3691718191 3692970391 3677909003 3689477811 3638603893 3691966651 3692970391 3692970391 3692970391 3681343828 3576516275 3678811171 3690448258 3690135313 3687076307 3692970391 3692970391 3692970391 3659449541 3692970391 3677282527 369...
result:
ok 100 numbers
Test #28:
score: 0
Accepted
time: 3ms
memory: 44752kb
input:
50 100 794804 326387 72887 924307 232451 519528 601019 407798 56835 594796 65959 496043 671546 207428 101058 826245 496147 131382 293881 779360 885979 832974 511964 428055 431364 579226 578335 524555 366245 381871 723034 7587 343799 218210 979146 842118 372890 518159 660686 192290 32334 698453 54353...
output:
5130008628 4808728036 4975217735 5026093311 5124798868 5078109332 4900978059 5118767978 5118735484 5070095030 5111926749 4947276146 5078258499 5114790747 5121109765 4995857479 5073437520 4985034828 5008414458 5127352388 5113848491 5068341358 5116516098 5114753764 4902482956 5130008628 5124417520 492...
result:
ok 50 numbers
Test #29:
score: 0
Accepted
time: 1048ms
memory: 82420kb
input:
500000 1 54323 737748 903520 1 1 692152 810006 1 1 12758 725821 1 1 127813 525491 1 1 872352 906159 1 1 10758 527461 1 1 778715 934980 1 1 320837 869940 1 1 224623 345649 1 1 7817 31142 1 1 991366 991656 1 1 312156 778301 1 1 516424 673463 1 1 824263 896790 1 1 160414 565103 1 1 994004 999732 1 1 30...
output:
54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 54323000000 ...
result:
ok 500000 numbers
Test #30:
score: 0
Accepted
time: 1825ms
memory: 93288kb
input:
500000 3 695487 984478 270897 451761 850596 1 1 578083 877776 3 1 2 3 41753 70082 2 1 3 33050 414469 3 1 2 3 774680 804379 2 1 3 554914 686301 2 1 3 745174 897081 2 1 3 80593 401682 1 2 236530 874618 3 1 2 3 865188 934191 2 1 2 859083 901216 3 1 2 3 279481 824621 1 1 547685 831541 1 2 440186 804390 ...
output:
1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 1950858098276 195085...
result:
ok 500000 numbers
Test #31:
score: 0
Accepted
time: 1987ms
memory: 86236kb
input:
500000 10 618236 832638 491856 55752 913414 585340 641276 908682 14966 68048 662071 726999 2 5 10 40420 760055 4 1 4 6 7 276419 794377 3 4 5 8 770146 823252 4 1 5 6 9 124185 421654 1 4 131154 776049 4 1 2 5 6 287480 462790 1 5 695915 818653 3 3 4 6 543730 827663 5 1 2 3 4 10 804167 888924 1 10 44771...
output:
5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 5130156345766 513015...
result:
ok 500000 numbers
Test #32:
score: -100
Wrong Answer
time: 1929ms
memory: 89684kb
input:
500000 100 531578 962055 401637 211882 646623 341951 426441 48942 94692 272556 493763 372568 765186 577287 522742 186973 618149 248670 160952 478660 401263 175634 830548 968104 766067 419353 868233 854970 194746 406781 822984 681597 216834 409690 79545 669896 302841 316516 446647 874184 730374 19279...
output:
44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 44504830120883 ...
result:
wrong answer 1st numbers differ - expected: '44504829146387', found: '44504830120883'