Submission #573461

#TimeUsernameProblemLanguageResultExecution timeMemory
573461perchutsHoliday (IOI14_holiday)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) (int) x.size() #define endl '\n' #define pb push_back #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); // #include "holiday.h" using namespace std; using ll = long long; using ull = unsigned long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; const int inf = 2e9+1; const int mod = 1e9+7; const int maxn = 1e5+100; template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; } template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; } //dp[i][j]: visito as cidades [i,j] (i<=start<=j). vamos gastar j-i + j-start dias andando //logo, queremos a soma dos max(0,min(d - (2j - start - i),j-i+1)) maiores numeros entre [i,j]. //igualzinho o cake3, mas nao da pra usar persistencia nesse por causa da memoria... //preciso achar os m maiores numeros entre [i,j] em log pair<ll,int> seg[4*maxn]; ll v[maxn]; vector<int>ord; int n, _ord[maxn]; void build(int i,int l,int r){ if(l==r){ seg[i] = {v[ord[l]],1}; return; } int md = (l+r)/2; build(2*i,l,md), build(2*i+1,md+1,r); seg[i].first = seg[2*i].first + seg[2*i+1].first; seg[i].second = seg[2*i].second + seg[2*i+1].second; } int curL, curR, st; ll ans = 0; void update(int i,int l,int r,int x,bool type){ if(l>x||r<x)return; if(l==r){ seg[i] = (type?make_pair(v[ord[l]],1):make_pair(0ll,0)); return; } int md = (l+r)/2; update(2*i,l,md,x,type), update(2*i+1,md+1,r,x,type); seg[i].first = seg[2*i].first + seg[2*i+1].first; seg[i].second = seg[2*i].second + seg[2*i+1].second; } ll query(int i,int l,int r,int qnt){ if(l==r)return qnt?seg[i].first:0; int md = (l+r)/2; if(seg[2*i+1].second>=qnt)return query(2*i+1,md+1,r,qnt); return seg[2*i+1].first + query(2*i,l,md,qnt-seg[2*i+1].second); } ll query(int l,int r,int d){ while(curL<l)update(1,1,n,_ord[curL],0),curL++; while(curL>l)curL--,update(1,1,n,_ord[curL],1); while(curR<r)curR++,update(1,1,n,_ord[curR],1); while(curR>r)update(1,1,n,_ord[curR],0),curR--; return query(1,1,n,d); } void compute(int l,int r,int lx,int rx,int d){ if(l>r)return; int md = (l+r)/2; ll best = -1, opt = -1; for(int i=lx;i<=min(md,rx);++i){ ll cur = query(i,md, max(0,max(d - (2*md - st - i),d - (md + st - 2*i)))); if(ckmax(best,cur))opt = i; } assert(opt!=-1); ckmax(ans,best); compute(l,md-1,lx,opt,d), compute(md+1,r,opt,rx,d); } ll findMaxAttraction(int N, int start, int d, int attraction[]) { ++start, n = N; for(int i=0;i<n;++i)v[i+1] = ll(attraction[i]); v[0] = -1; ord.resize(n+1),iota(all(ord),0),sort(all(ord), [&](int x,int y){ return v[x] < v[y]; }); for(int i=1;i<=n;++i)_ord[ord[i]] = i; build(1,1,n); curL = 1, curR = n, st = start; compute(st,n,1,st,d); return ans; } int attraction[maxn]; int main(){ int n, start, d;cin>>n>>start>>d; for(int i=0;i<n;++i)cin>>attraction[i]; cout<<findMaxAttraction(n,start,d,attraction)<<endl; }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccncDiQg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZtWeEg.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status