QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#305274 | #7622. Yet Another Coffee | NemanjaSo2005 | WA | 1ms | 9548kb | C++14 | 3.3kb | 2024-01-15 00:00:14 | 2024-01-15 00:00:16 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N;
struct pstslog{
ll suma=0,kol=0;
int d1=0,d2=0;
}pst[30000000];
int pss=0;
int novi(){
pss++;
pst[pss].suma=0;
pst[pss].kol=0;
pst[pss].d1=pst[pss].d2=0;
return pss;
}
int pvrem=0,root[200005];
void psupdate(int gde,int upd,int lc,int dc,int stavi){
if(lc==dc){
pst[gde].suma+=stavi;
pst[gde].kol++;
return;
}
int sred=(lc+dc)/2;
if(upd<=sred){
int koji=novi();
pst[koji]=pst[pst[gde].d1];
pst[gde].d1=koji;
psupdate(koji,upd,lc,sred,stavi);
}
else{
int koji=novi();
pst[koji]=pst[pst[gde].d2];
pst[gde].d2=koji;
psupdate(koji,upd,sred+1,dc,stavi);
}
pst[gde].suma=pst[pst[gde].d1].suma+pst[pst[gde].d2].suma;
pst[gde].kol=pst[pst[gde].d1].kol+pst[pst[gde].d2].kol;
/*
cout<<gde<<" "<<lc<<" "<<dc<<" "<<upd<<" "<<stavi<<endl;
cout<<pst[gde].suma<<" "<<pst[gde].kol<<endl;*/
return;
}
void pstupdate(int koji,int stavi){
pvrem++;
root[pvrem]=novi();
pst[root[pvrem]]=pst[root[pvrem-1]];
psupdate(root[pvrem],koji,1,(1<<30),stavi);
}
ll get(int poz,int k){
//cout<<k<<endl;
//cout<<poz<<" "<<pst[poz].suma<<" "<<pst[poz].kol<<endl;
if(k<=0)
return 0;
if(pst[poz].kol<k)
return 1e18;
if(pst[poz].kol==k)
return pst[poz].suma;
if(pst[pst[poz].d1].kol>=k)
return get(pst[poz].d1,k);
return pst[pst[poz].d1].suma+get(pst[poz].d2,k-pst[pst[poz].d1].kol);
}
ll suma(int gde,int k){
if(N-gde+1<k)
exit(-1);
int v=N-gde+1;
v=root[v];
return get(v,k);
}
const int maxn=2e5+5;
ll M,suf[maxn],cena[maxn],res[maxn];
int pitaj(int idx,int s,int e){
ll mcena=1e18;
int ret;
for(int i=e;i>=s;i--){
if(N-i<idx-1)
continue;
ll v=0;
v+=cena[i];
v-=suf[i];
v+=suma(i+1,idx-1);
if(v<mcena){
mcena=v;
ret=i;
}
}
res[idx]=mcena;
// cout<<idx<<" "<<ret<<" "<<cena[ret]<<" "<<suf[ret]<<" "<<suma(ret+1,idx-1)<<endl;
return ret;
}
void resi(int brl,int brr,int lb,int ub){
if(brr<brl)
return;
int mid=(brl+brr)/2;
int gde=pitaj(mid,lb,ub);
resi(brl,mid-1,gde,ub);
resi(mid+1,brr,lb,gde);
}
void solve(){
pst[0].suma=pst[0].kol=0;
pst[0].d1=pst[0].d2=0;
pss=0;
cin>>N>>M;
for(int i=1;i<=N;i++)
cin>>cena[i];
int a,b;
while(M--){
cin>>b>>a;
suf[b]+=a;
}
for(int i=N-1;i>=1;i--)
suf[i]+=suf[i+1];
for(int i=N;i>=1;i--)
pstupdate(cena[i],cena[i]);
//cout<<suma(5,5)<<endl;
//return;
/*for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++){
cout<<i<<" "<<j<<" "<<suma(i,j)<<endl;
}
return;*/
resi(1,N,1,N);
for(int i=1;i<=N;i++)
cout<<res[i]<<" ";
cout<<"\n";
}
void reset(){
for(int i=1;i<=N;i++){
suf[i]=0;
cena[i]=0;
res[i]=0;
}
for(int i=0;i<=pvrem+3;i++)
root[i]=0;
for(int i=0;i<=pss;i++){
pst[i].d1=pst[i].d2=0;
pst[i].suma=0;
pst[i].kol=0;
}
pvrem=0;
pss=0;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--){
solve();
reset();
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 9548kb
input:
5 10 14 17 37 59 65 53 73 68 177 160 111 10 177 5 193 2 30 3 63 2 339 3 263 5 178 2 190 9 23 10 328 10 200 9 8 3 391 6 230 12 9 152 306 86 88 324 59 18 14 42 260 304 55 3 50 2 170 1 252 7 811 1 713 7 215 10 201 4 926 8 319 19 20 182 74 180 201 326 243 195 31 170 263 284 233 48 166 272 281 179 116 31...
output:
-2596 -2559 -2506 -2447 -2382 -2314 -2241 -2130 -1970 -1793 -3505 -3491 -3473 -3431 -3376 -3317 -3231 -3143 -2883 -2579 -2273 -1949 -6527 -6496 -6448 -6374 -6258 -6092 -5922 -5743 -5563 -5368 -5167 -4934 -4691 -4428 -4156 -3875 -3591 -3272 -2946 -3219 -2987 -2572 -2140 -1707 -1238 -768 -274 243 1...
result:
wrong answer 68th numbers differ - expected: '-799', found: '999999999999999134'