Submission #1064735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064735		NemanjaSo2005	Holiday (IOI14_holiday)	C++17	24 / 100	5061 ms	3532 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;
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}});
   }
}
void processq(pair<pair<int,int>,pair<int,int>> x){
   int l=x.f.f;
   int r=x.f.s;
   int k=x.s.f;
   int idx=x.s.s;
   ll v=summaxk(l,r,k);
   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());
   for(auto x:upiti)
      processq(x);
   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++;
   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 'long long int summaxk(int, int, int)':
holiday.cpp:18:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |       while(PQ.size()>k){
      |             ~~~~~~~~~^~
holiday.cpp: In function 'void makestep()':
holiday.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for(int i=0;i<V.size();i++){
      |                ~^~~~~~~~~
holiday.cpp:92:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<slog>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for(int i=0;i<V.size();i++)
      |                ~^~~~~~~~~

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