이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
pll operator+(const pll &a,const pll &b){return MP(a.F+b.F,a.S+b.S);}
struct node
{
int cnt,l,r;
ll sum;
}mem[2500000];
int memtp,ti[100005],n,start,d;
vector<int> v;
int newnode(node tmp=node{0,-1,-1,0LL})
{
return mem[memtp]=tmp,memtp++;
}
int CNT(int rt){return !~rt?0:mem[rt].cnt;}
ll SUM(int rt){return !~rt?0:mem[rt].sum;}
int lch(int rt){return !~rt?-1:mem[rt].l;}
int rch(int rt){return !~rt?-1:mem[rt].r;}
void up(int rt)
{
mem[rt].cnt=CNT(lch(rt))+CNT(rch(rt));
mem[rt].sum=SUM(lch(rt))+SUM(rch(rt));
}
int modify(int x,int l,int r,int rt)
{
if(!~rt) rt=newnode();
else rt=newnode(mem[rt]);
if(l==r)
return ++mem[rt].cnt,mem[rt].sum+=v[l],rt;
int m=l+r>>1;
if(x<=m) mem[rt].l=modify(x,l,m,mem[rt].l);
else mem[rt].r=modify(x,m+1,r,mem[rt].r);
return up(rt),rt;
}
int kth(int L,int R,int l,int r,int k)
{
if(l==r) return l;
int m=l+r>>1;
if(CNT(rch(R))-CNT(rch(L))>=k)
return kth(rch(L),rch(R),m+1,r,k);
return kth(lch(L),lch(R),l,m,k-CNT(rch(R))+CNT(rch(L)));
}
pll query(int L,int R,int ql,int qr,int l,int r)
{
if(ql<=l&&qr>=r)
return MP(CNT(R)-CNT(L),SUM(R)-SUM(L));
int m=l+r>>1;
if(qr<=m) return query(lch(L),lch(R),ql,qr,l,m);
if(ql>m) return query(rch(L),rch(R),ql,qr,m+1,r);
return query(lch(L),lch(R),ql,qr,l,m)+query(rch(L),rch(R),ql,qr,m+1,r);
}
ll wei(int l,int r,int k)
{
if(k<=0) return 0;
if(l>r) swap(l,r);
k=min(k,r-l+1);
int num=kth(ti[l-1],ti[r],0,v.size()-1,k);
pll val=MP(0,0);
if(num+1<v.size()) val=query(ti[l-1],ti[r],num+1,v.size()-1,0,v.size()-1);
return val.S+(k-val.F)*v[num];
}
ll dp(int tl,int tr,int l,int r,int rv)
{
if(l>r) return 0;
int m=l+r>>1;
ll rt=-1,pl=tl;
for(int i=tl;i<=tr;++i)
{
ll x;
if(rv) x=wei(n-i+1,n-m+1,d-2*(m-(n-start+1))-((n-start+1)-i));
else x=wei(i,m,d-2*(m-start)-(start-i));
if(x>rt) rt=x,pl=i;
}
return max({rt,dp(tl,pl,l,m-1,rv),dp(pl,tr,m+1,r,rv)});
}
long long int findMaxAttraction(int _n, int _start, int _d, int attraction[])
{
n=_n,start=_start,d=_d;
for(int i=0;i<n;++i)
v.pb(attraction[i]);
sort(ALL(v)),v.resize(unique(ALL(v))-v.begin()),ti[0]=-1;
for(int i=1;i<=n;++i)
ti[i]=modify(lower_bound(ALL(v),attraction[i-1])-v.begin(),0,v.size()-1,ti[i-1]);
++start;
return max(dp(1,start,start,n,0),dp(1,n-start+1,n-start+1,n,1));
}
컴파일 시 표준 에러 (stderr) 메시지
holiday.cpp: In function 'int modify(int, int, int, int)':
holiday.cpp:50:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
holiday.cpp: In function 'int kth(int, int, int, int, int)':
holiday.cpp:59:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
holiday.cpp: In function 'pll query(int, int, int, int, int, int)':
holiday.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
holiday.cpp: In function 'll wei(int, int, int)':
holiday.cpp:82:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(num+1<v.size()) val=query(ti[l-1],ti[r],num+1,v.size()-1,0,v.size()-1);
~~~~~^~~~~~~~~
holiday.cpp: In function 'll dp(int, int, int, int, int)':
holiday.cpp:89:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m=l+r>>1;
~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |