QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #91804 | #4947. 混合果汁 | Alex10086 | 0 | 0ms | 0kb | C++14 | 2.6kb | 2023-03-29 16:40:26 | 2023-03-29 16:40:28 |
Judging History
answer
#include<bits/stdc++.h>
//#define int long long
//#define FILE
using namespace std;
struct que{
int g,l,id;
};
struct edge{
int v,w,mx,id;
};
int ans[200005],num[200005],cnt[200005],tot,id[200005];
int n,q;
struct TR
{
int ls,rs,totv,totl,w;
}t[400005];
int top;
int upd(int rt,int le,int ri,edge x,int k)
{
if (!rt) rt=++top;
if (le==ri)
{
t[rt].totl+=x.mx*k,t[rt].totv+=x.mx*x.w*k;
if (k==1) t[rt].w=x.w;
else t[rt].w=998244353;
return rt;
}
int m=(le+ri)>>1;
if (x.id<=m) t[rt].ls=upd(t[rt].ls,le,m,x,k);
else t[rt].rs=upd(t[rt].rs,m+1,ri,x,k);
t[rt].totv=t[t[rt].ls].totv+t[t[rt].rs].totv,t[rt].totl=t[t[rt].ls].totl+t[t[rt].rs].totl;
return rt;
}
int qry(int rt,int v)
{
if (v<=0) return 0;
if (!t[rt].ls&&!t[rt].rs) return v/t[rt].w;
if (t[t[rt].ls].totv>v) return qry(t[rt].ls,v);
else return t[t[rt].ls].totl+qry(t[rt].rs,v-t[t[rt].ls].totv);
}
int rt;
void solve(int l,int r,vector<edge> a,vector<que> q)
{
if (l>r)
{
for (auto i : q) ans[i.id]=-1;
return ;
}
if (l==r)
{
for (auto i : q) ans[i.id]=cnt[l];
return ;
}
int m=((l+r)>>1)+1;
vector<edge> a1,a2;
for (auto i : a)
{
if (i.v<m) a1.emplace_back(i),rt=upd(rt,1,tot,i,-1);
else a2.emplace_back(i);
}
vector<que> q1,q2;
bool pd=0;
for (auto i : q)
{
pd=1;
int res=qry(rt,i.g);
if (i.l>res) q1.emplace_back(i);
else q2.emplace_back(i);
}
if (!pd)
{
for (auto i : a1) rt=upd(rt,1,tot,i,1);
return ;
}
solve(m,r,a2,q2);
for (auto i : a1) rt=upd(rt,1,tot,i,1);
solve(l,m-1,a1,q1);
}
vector<edge> a;
bool cmp(int x,int y){return num[x]<num[y];}
bool cmp2(edge a,edge b){return a.v<b.v;}
bool cmp3(int x,int y){return a[x-1].w<a[y-1].w;}
void init()
{
sort(id+1,id+1+n,cmp);
tot=1;
for (int i=2;i<=n+1;i++)
{
if (num[id[i]]!=num[id[i-1]]) cnt[tot]=num[id[i-1]],num[id[i-1]]=tot++;
else num[id[i-1]]=tot;
}
tot--;
sort(id+1,id+1+n,cmp3);
for (int i=1;i<=n;i++) a[i-1].v=num[i],a[i-1].id=id[i];
}
signed main()
{
#ifdef FILE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
scanf("%d%d",&n,&q);
for (int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d%d",&num[i],&x,&y),id[i]=i;
a.emplace_back(edge{0,x,y,0});
}
a.emplace_back(edge{0,1,998244353,0});
num[++n]=-1,id[n]=n;
init();
vector<que> qe;
for (int i=1;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
qe.emplace_back(que{x,y,i});
}
for (auto i : a) rt=upd(rt,1,tot,i,1);
solve(1,tot,a,qe);
for (int i=1;i<=q;i++) printf("%d\n",ans[i]);
system("pause");
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
10 10 44894 45296 4296 96357 95394 34037 23283 23930 43005 43330 43000 38959 47744 48195 10266 27116 26946 81420 60433 60242 95603 31529 32036 81788 48404 48829 81712 77157 76571 51380 90171111 9412 1063760163 7125 1507224419 3799 667070329 949 1315536036 7388 854846064 8708 990959616 3410 59788892 ...
output:
result:
Test #2:
score: 0
Dangerous Syscalls
input:
10 10 71203 70943 96030 2907 3366 43446 59057 58730 29943 20030 19971 5151 54659 54133 16206 61347 60820 58102 73802 73343 32955 49325 49519 51020 53790 53260 12493 60357 60341 33443 1039324449 4656 396371768 1370 1385376577 1519 1468730283 4687 1728094263 8256 124371528 7039 1505613387 3776 1556326...
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
10 10 84357 83668 41893 56186 56253 48151 26943 27631 23412 58381 58408 88250 58116 57651 69178 28461 28256 96445 80486 80295 1631 8221 8761 35636 6481 6525 77888 1954 2227 24475 1602937961 2278 1977095578 1844 596473909 4801 1449483215 2251 111122583 1909 1676272921 6864 757255225 1309 765268006 55...
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
500 500 97511 97491 87760 9461 10239 52855 94832 94531 16881 96733 95943 71346 61574 61071 22147 95578 94693 34784 87171 86345 70311 67121 67002 20252 59176 58790 43278 43556 43112 15506 98999 97920 23186 65677 65753 91043 98152 97786 55624 29880 30171 50326 88425 87521 63173 98803 97967 11869 67562...
output:
result:
Test #5:
score: 0
Dangerous Syscalls
input:
500 500 23816 24039 79489 16015 16211 62265 30602 30332 3819 73433 72915 37538 68488 68009 28087 29806 29665 11466 536 1446 7663 84917 84485 89488 64562 64320 74063 26755 26882 97574 51437 51420 32679 12891 13137 17568 49432 49555 28691 79290 79043 94860 39095 38918 77711 25127 25774 66413 54844 544...
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
500 500 50124 50588 71219 22568 23083 71674 66377 66033 90761 50132 49887 3730 75403 75046 34027 64037 63539 88153 13905 14547 45019 2710 2968 58721 69948 69850 4845 9954 10653 79637 3874 3821 42173 60109 59621 44097 712 1324 1757 28696 28914 39390 89768 89414 92248 51455 51580 20953 42126 42421 825...
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
5000 5000 63279 63312 17082 75847 75069 76378 34262 33934 84230 88484 88323 86830 78860 78465 86999 31151 30976 26492 20589 20499 13695 61610 61209 43337 22639 23115 70239 51556 51538 70669 80097 79522 46919 33717 33813 7359 76356 76159 38293 53400 53448 11655 65102 64711 99517 14617 15033 48225 857...
output:
-1 -1 -1 -1 99978 99665 -1 -1 98867 96710 -1 91338 -1 -1 99960 -1 -1 -1 96173 96710 98309 90906 -1 97029 -1 -1 99332 -1 -1 99665 -1 99332 90859 99332 99332 -1 96710 -1 -1 96735 -1 -1 96283 -1 96173 99978 -1 -1 -1 -1 -1 99332 96283 -1 -1 96710 -1 90859 99332 -1 99206 -1 90906 -1 -1 96173 -1 99665 998...
result:
Test #8:
score: 0
Dangerous Syscalls
input:
5000 5000 89587 88861 8812 82401 82041 85788 70036 69734 71168 65183 65295 53021 85775 85403 92940 65382 64849 3174 33958 33600 51051 79406 78692 12569 28025 28644 1020 34755 35308 52733 32535 33022 56413 80935 80197 33888 27637 27928 11359 2806 3319 56189 15772 16108 14051 40945 40839 2766 73051 72...
output:
-1 -1 97384 94922 -1 -1 96330 96330 99327 97384 -1 99805 98079 -1 99405 98797 -1 -1 -1 -1 96330 -1 94922 -1 97384 -1 97516 96738 97516 97384 98079 98797 99794 96330 -1 98163 -1 98361 96738 -1 -1 -1 94922 -1 -1 96330 -1 97384 97384 -1 97384 96738 99805 98797 94922 -1 99013 99995 96594 -1 -1 -1 96605 ...
result:
Test #9:
score: 0
Dangerous Syscalls
input:
5000 5000 15892 16409 541 88954 88914 95197 5807 6535 58106 41883 42267 19213 92690 92341 98880 99613 98821 79860 47327 47701 88407 97202 97175 81805 33411 33174 31805 17954 18079 34796 84977 84422 65906 28149 28582 60417 78921 78697 84430 52216 52190 718 66445 66604 28589 67273 66646 57310 60332 60...
output:
96236 99705 -1 -1 99896 -1 -1 -1 -1 97234 97694 -1 96236 98219 -1 -1 -1 97234 -1 97234 97234 96728 96798 97234 -1 -1 99778 97234 99920 96798 -1 97234 98376 96917 -1 99674 97536 -1 99259 98219 96798 98219 -1 -1 97231 -1 -1 -1 -1 -1 98219 97234 98219 99896 97234 99674 -1 -1 -1 -1 97694 -1 -1 99607 972...
result:
Test #10:
score: 0
Dangerous Syscalls
input:
100000 100000 42200 1 27746 92275 1 95508 34071 1 4602 41581 1 15081 45044 1 18582 92340 1 85409 99604 1 77335 4816 1 33840 23227 1 56542 60696 1 70815 25760 1 14994 80735 1 51037 38797 1 29184 62590 1 1153 75943 1 16859 37414 1 89590 75399 1 75367 41889 1 86946 30201 1 56744 57497 1 1622 47699 1 45...
output:
-1 98416 99926 98987 98493 98699 99837 99347 -1 98909 97309 98362 -1 99295 98940 97466 -1 98449 97297 97975 97508 -1 97213 97683 98411 -1 98625 -1 97913 99481 -1 99481 99802 99286 99199 97001 98588 -1 -1 98625 99738 97812 97861 98704 98162 98784 -1 98137 99595 99481 -1 98325 97464 99247 -1 97645 997...
result:
Test #11:
score: 0
Dangerous Syscalls
input:
100000 100000 7968 1 5547 21597 1 61890 43551 1 28126 81015 1 54731 12389 1 10333 52046 1 888 16887 1 4063 69669 1 69416 27076 1 48250 94118 1 79558 69148 1 9482 45952 1 74121 2260 1 75168 89551 1 9153 26536 1 72022 18513 1 20814 99132 1 43407 6004 1 3262 8405 1 52263 40165 1 25142 38974 1 6581 9379...
output:
98027 99617 99796 98814 99151 -1 -1 -1 99741 99633 99563 97766 98843 -1 99337 -1 -1 98998 98858 97301 97966 97078 99757 97439 -1 99645 98033 99397 97750 98040 98603 99594 -1 99741 99485 98997 99596 98049 96771 99924 97145 -1 98748 98778 99813 97344 99909 99965 97469 97046 97270 97259 97911 99371 996...
result:
Test #12:
score: 0
Dangerous Syscalls
input:
100000 100000 73740 1 83353 50923 1 28273 53031 1 51649 20445 1 94380 79738 1 2084 11753 1 16371 34174 1 30794 34518 1 4989 30926 1 39957 27537 1 88301 12532 1 3970 11169 1 97206 65727 1 21148 16507 1 17153 77134 1 27181 99615 1 52042 22862 1 11447 70124 1 19582 86613 1 47781 22834 1 48662 30249 1 6...
output:
98199 99444 -1 -1 98684 99925 97848 99093 97166 99176 97196 98647 96976 99646 -1 99394 97248 99676 97176 98528 99680 -1 99135 99435 98089 -1 99190 -1 98442 -1 98570 98969 -1 97188 97414 98245 98599 99211 99467 99687 99979 -1 98218 97342 -1 -1 98647 -1 98909 96958 97467 98827 97259 99605 -1 98583 -1 ...
result:
Test #13:
score: 0
Dangerous Syscalls
input:
100000 100000 39507 39717 1 94659 94280 1 59879 59543 1 93838 93577 1 51461 51462 1 40565 40443 1 60959 61262 1 98462 98180 1 29190 29481 1 25153 25127 1 80713 80726 1 79490 78949 1 64818 64585 1 72183 71595 1 47149 47573 1 41051 40748 1 2229 2783 1 33661 33330 1 47327 47662 1 88486 87626 1 47016 47...
output:
99488 -1 99398 99626 99359 -1 98918 99106 99698 99440 -1 98491 98982 99319 99121 -1 99646 59237 7814 98696 99560 72787 98566 99196 98984 98622 98982 91001 99296 86623 98976 61060 99812 99337 99404 -1 98567 98774 -1 98634 98833 99958 99903 -1 -1 98802 -1 98726 98899 99275 99160 98506 98441 98506 9895...
result:
Test #14:
score: 0
Dangerous Syscalls
input:
100000 100000 5275 5538 1 61041 61110 1 99313 99044 1 85589 84957 1 68747 68856 1 76141 75726 1 94382 93415 1 92950 92388 1 92657 91806 1 33153 33553 1 61811 61327 1 47530 48009 1 43022 42959 1 95703 94871 1 23826 23764 1 56869 56813 1 20436 20633 1 52549 52416 1 30580 30463 1 43088 42983 1 99280 98...
output:
98731 98859 99740 99774 97043 98607 99051 99718 20749 99506 99202 98613 99692 65387 99801 98896 87048 17819 99067 -1 99632 98702 99956 99475 99520 99129 99778 99663 98990 -1 99562 99164 99846 98893 9782 99431 99573 98911 99468 99269 99692 98638 99172 99219 -1 98657 99699 -1 -1 99796 99283 99305 9988...
result:
Test #15:
score: 0
Dangerous Syscalls
input:
100000 100000 84200 84282 1 80702 79927 1 6628 7347 1 15688 15873 1 89491 88670 1 78830 78445 1 34485 34619 1 46334 46836 1 8811 9395 1 82755 82864 1 19129 19629 1 89181 89162 1 96871 96167 1 43925 43485 1 75842 75153 1 35849 36331 1 82285 81414 1 95215 94338 1 30484 30283 1 88615 88490 1 1990 2232 ...
output:
-1 98941 61531 99163 99336 99961 -1 99969 99229 98992 66369 99764 99694 99125 99922 -1 75369 -1 -1 99305 99031 98388 98474 99447 99098 85136 99471 99336 99579 99002 -1 -1 99948 98648 99727 6908 -1 -1 99228 98571 99951 98861 -1 99510 99225 75376 99103 99459 29588 99311 99528 98537 99980 98517 8336 99...
result:
Test #16:
score: 0
Dangerous Syscalls
input:
100000 100000 63122 62926 59954 360 645 55147 13947 14650 36061 45790 45788 44496 10232 10583 99860 81520 81164 83473 74592 73823 23432 99722 99285 58771 24969 24886 55130 32353 32175 29887 76450 75931 27284 30828 31415 11386 50715 50474 26579 92150 92098 57766 27853 27542 75723 14829 14850 84525 44...
output:
-1 -1 98848 93718 95362 -1 93718 93718 92935 -1 -1 -1 92749 99228 98368 93718 97459 -1 93718 93718 92936 -1 -1 97794 -1 93732 -1 -1 93718 -1 -1 -1 -1 93718 95250 93718 -1 -1 99463 -1 -1 93674 93718 -1 93732 96866 99541 93732 93732 93674 -1 93732 -1 -1 -1 93718 -1 93732 -1 93718 93718 99776 -1 93732 ...
result:
Test #17:
score: 0
Dangerous Syscalls
input:
100000 100000 42044 42571 35143 20021 20462 83375 21266 21953 96879 75892 75704 43075 30976 31396 17677 84210 83883 13520 14695 15027 35496 53106 52733 66472 41127 41476 47481 81954 81486 76081 33767 34233 55764 72478 72568 90972 4560 4682 45783 40371 40711 91364 79869 79931 19332 93813 93368 48149 ...
output:
-1 97383 -1 -1 98024 -1 95280 95089 -1 -1 96931 95497 -1 -1 99352 96372 -1 97244 96919 -1 -1 -1 -1 -1 99324 -1 98024 98024 -1 -1 98398 98066 -1 98024 -1 -1 -1 94819 98035 96919 -1 94819 -1 -1 -1 -1 97793 98024 95497 -1 96813 96919 -1 97171 -1 -1 99632 99969 97102 96293 -1 -1 -1 -1 97250 98407 98614 ...
result:
Test #18:
score: 0
Dangerous Syscalls
input:
100000 100000 34120 34039 56199 92961 92165 16304 96474 96156 51162 44343 44155 24750 55177 54729 88470 54013 54039 81914 61486 61281 16236 65391 65324 58788 9975 10232 5223 73153 72682 13303 67307 67334 88990 87736 87013 33817 34048 33825 1519 13297 13760 97226 7215 7618 70214 35955 36240 39046 114...
output:
-1 95643 -1 -1 99535 94421 -1 -1 94127 -1 -1 96766 -1 -1 -1 95647 96856 99968 95647 -1 -1 99350 -1 -1 -1 94421 96223 -1 -1 95647 -1 -1 -1 -1 96086 -1 99626 -1 95634 96200 96882 -1 94127 -1 -1 -1 -1 94421 -1 -1 95643 -1 -1 96231 -1 -1 -1 -1 94421 -1 95621 94421 -1 -1 96766 98622 96856 -1 98484 -1 989...
result:
Test #19:
score: 0
Dangerous Syscalls
input:
100000 100000 13042 13684 31388 12618 12982 44532 3790 4458 11977 74445 74070 23330 75921 75641 6287 56703 56758 11960 1589 2485 28300 18775 18773 66489 26133 26822 97578 22751 22994 59497 24624 24635 17466 29383 29166 13399 87897 87033 20723 61522 61473 30820 59230 59007 13824 14935 14758 2671 7331...
output:
96055 99166 98324 -1 -1 99068 -1 96122 -1 97871 97315 98351 -1 -1 -1 -1 -1 -1 98507 90684 94416 -1 -1 97095 -1 99013 -1 -1 -1 -1 98954 97124 -1 -1 97082 -1 99068 -1 99068 -1 -1 99173 98733 99217 99076 97124 -1 97082 -1 -1 -1 -1 -1 96897 97095 96803 97086 97095 98078 -1 -1 96055 96640 96055 97082 -1 ...
result:
Test #20:
score: 0
Dangerous Syscalls
input:
100000 100000 91968 91328 6577 32279 32700 72759 11109 11860 72795 4544 4986 21909 96665 96455 24108 59393 59379 42011 41696 41689 40365 72163 72222 74189 42291 42312 89929 72353 72305 5688 81945 81937 45946 71034 70419 92986 41741 41340 39926 9744 10086 64417 11242 11396 57437 93919 93276 66299 351...
output:
-1 97383 94908 -1 98011 -1 -1 99261 -1 97719 97371 -1 -1 -1 94590 -1 97097 96939 -1 -1 -1 -1 -1 99644 -1 97406 -1 97057 -1 96044 -1 97928 -1 -1 97361 -1 -1 -1 -1 96939 98012 -1 -1 96939 -1 97800 99644 -1 -1 97107 97094 94590 -1 99247 97934 -1 98173 97461 99488 -1 97094 -1 -1 98869 -1 94617 -1 -1 -1 ...