QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305274#7622. Yet Another CoffeeNemanjaSo2005WA 1ms9548kbC++143.3kb2024-01-15 00:00:142024-01-15 00:00:16

Judging History

你现在查看的是最新测评结果

  • [2024-01-15 00:00:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9548kb
  • [2024-01-15 00:00:14]
  • 提交

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'