Submission #1235147

#TimeUsernameProblemLanguageResultExecution timeMemory
1235147ricardsjansonsNile (IOI24_nile)C++20
0 / 100
1163 ms150464 KiB
#include "nile.h" #include <bits/stdc++.h> #define ll long long using namespace std; int n; vector<int>w; const int N=1<<17; int segt[N*2]{}; void upd(int i,int dw){ i+=N; segt[i]=dw; for(i/=2;i;i/=2){ segt[i]=max(segt[i*2],segt[i*2+1]); } } map<pair<int,int>,int>mem; int maxdw(int l,int r,bool x=1){ if(x){ l+=N; r+=N; } if(mem.count({l,r})){ return mem[{l,r}]; } int&res=mem[{l,r}]; if(l<=r){ if(l%2==1){ res=max(res,segt[l++]); } if(r%2==0){ res=max(res,segt[r--]); } l/=2; r/=2; } res=max(res,maxdw(l,r,0)); return res; } ll f(int d){ ll res=0; for(int i=0,j=0;i<n;i=++j){ int l=i,r=n-1; upd(i,0); while(l<r){ int mid=(l+r+1)/2; if(maxdw(i,mid)<=d){ l=mid; }else{ r=mid-1; } } if(i){ upd(i,w[i]-w[i-1]); } j=l; res+=j-i+1; if((j-i)%2==0){ res++; } } return res; } vector<ll> calculate_costs(vector<int>W,vector<int>A,vector<int>B,vector<int>E) { n=A.size(); sort(W.begin(),W.end()); w=W; for(int i=1;i<n;i++){ upd(i,w[i]-w[i-1]); } vector<ll>r; for(int d:E){ r.push_back(f(d)); } return r; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...