Submission #1064783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064783		NemanjaSo2005	Holiday (IOI14_holiday)	C++17	100 / 100	1014 ms	13768 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=1e5+5;
int N,niz[maxn],D,poc;
priority_queue<int> PQ;
ll suma,res=0;
int tsz=1;
struct pstslog{
   int d[2]={0,0};
   int br=0;
   ll zbir=0;
} st[1500000];
int make(){
   ++tsz;
   return tsz;
}
void add(int vred,int kol,int gde=1,int lc=1,int dc=(1<<30)){
//   cout<<gde<<endl;
   if(lc==dc){
      //cout<<"DODAJ NA "<<vred<<" "<<kol<<endl;
      st[gde].br+=kol;
      st[gde].zbir=(ll)st[gde].br*lc;
      return;
   }
   int sred=(lc+dc)/2;
   if(vred<=sred){
  //    cout<<"LEFT"<<endl;
      if(st[gde].d[0]==0)
         st[gde].d[0]=make();
      add(vred,kol,st[gde].d[0],lc,sred);
   }
   else{
    //  cout<<"RIGHT"<<endl;
      if(st[gde].d[1]==0)
         st[gde].d[1]=make();
      add(vred,kol,st[gde].d[1],sred+1,dc);
   }
   int d0=st[gde].d[0];
   int d1=st[gde].d[1];
   st[gde].br=st[d0].br+st[d1].br;
   st[gde].zbir=st[d0].zbir+st[d1].zbir;
   return;
}
ll sumtop(int k,int gde=1){
   if(gde==0 or k<=0)
      return 0;
   if(k>=st[gde].br)
      return st[gde].zbir;
   int d0=st[gde].d[0];
   int d1=st[gde].d[1];
   return sumtop(k,d1)+sumtop(k-st[d1].br,d0);
}
/*ll summaxk(int l,int r,int k){
   while(PQ.size())
      PQ.pop();
   ll s=0;
   for(int i=l;i<=r;i++){
      s+=niz[i];
      PQ.push(-niz[i]);
      while(PQ.size()>k){
         s+=PQ.top();
         PQ.pop();
      }
   }
   return s;
}*/
struct slog{
   int l,r,m,poz;
   ll v;
   int lj,rj;
};
vector<slog> V,novi;
void update(int idx,ll vred,int j){
   if(V[idx].v>=vred)
      return;
   V[idx].v=vred;
   V[idx].poz=j;
   res=max(res,vred);
}
void split(int idx){
   slog a,b,x=V[idx];
   a.l=x.l;
   a.r=x.m-1;
   a.m=(a.l+a.r)/2;
   a.lj=x.lj;
   a.rj=x.poz;
   a.v=0;
   a.poz=a.rj;

   b.l=x.m+1;
   b.r=x.r;
   b.m=(b.l+b.r)/2;
   b.lj=x.poz;
   b.rj=x.rj;
   b.v=0;
   b.poz=b.rj;

   if(a.l<=a.r)
      novi.push_back(a);
   if(b.l<=b.r)
      novi.push_back(b);
}
vector<pair<pair<int,int>,pair<int,int>>> upiti;
void makeq(int idx){
   for(int j=V[idx].lj;j<=V[idx].rj;j++){
      int d=V[idx].m-j+min(poc-j,V[idx].m-poc);
      if(d>=D)
         continue;
      int k=D-d;
      upiti.push_back({{j,V[idx].m},{k,idx}});
   }
}
int lb,rb;
void processq(pair<pair<int,int>,pair<int,int>> x){
   int l=x.f.f;
   int r=x.f.s;

   while(lb<l){
      add(niz[lb],-1);
      lb++;
   }
   while(rb<=r){
      add(niz[rb],1);
      rb++;
   }

   int k=x.s.f;
   int idx=x.s.s;
/*
   cout<<"SEGMENTNO"<<endl;
   for(int i=1;i<=tsz;i++){
      cout<<i<<": "<<st[i].br<<" | "<<st[i].zbir<<" | "<<st[i].d[0]<<" "<<st[i].d[1]<<endl;
   }

   cout<<l<<" "<<r<<" "<<lb<<" "<<rb<<" "<<k<<endl;*/
   ll v=sumtop(k);/*
   cout<<v<<endl;

   exit(0);*/
   update(idx,v,l);
}
void makestep(){
   upiti.clear();
   for(int i=0;i<V.size();i++){
      makeq(i);
   }
   if(upiti.size()==0){
      V.clear();
      return;
   }
   sort(upiti.begin(),upiti.end());
   lb=rb=1;
   for(auto x:upiti)
      processq(x);
   while(lb<rb){
      add(niz[lb],-1);
      lb++;
   }
   novi.clear();
   for(int i=0;i<V.size();i++)
      split(i);
   V.clear();
   V=novi;
}
long long int findMaxAttraction(int n, int start, int ddd, int attraction[]) {
   N=n;
   for(int i=1;i<=N;i++)
      niz[i]=attraction[i-1];
   D=ddd;
   start++;
   if(start==1){
      for(int i=start;i>=1;i--){
      suma=0;
      while(PQ.size())
         PQ.pop();
      for(int j=i;j<start;j++){
         suma+=niz[j];
         PQ.push(-niz[j]);
      }
      for(int j=start;j<=N;j++){
         int d=j-i+min(start-i,j-start);
         if(d>=D)
            break;
         suma+=niz[j];
         PQ.push(-niz[j]);
         while(PQ.size()+d>D){
            suma+=PQ.top();
            PQ.pop();
         }
         res=max(res,suma);
      }
    }
    return res;

   }
   poc=start;
   slog a;
   a.l=start;
   a.r=N;
   a.lj=1;
   a.rj=start;
   a.m=(a.l+a.r)/2;
   a.poz=a.rj;
   a.v=0;
   V.push_back(a);
   while(V.size()){
      makestep();
   }
   return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void makestep()':
holiday.cpp:148:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
holiday.cpp:164:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |    for(int i=0;i<V.size();i++)
      |                ~^~~~~~~~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:190:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  190 |          while(PQ.size()+d>D){
      |                ~~~~~~~~~~~^~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53