oj.uz

Submission #140825

# Submission time Handle Problem Language Result Execution time Memory
140825 2019-08-05T12:05:18 Z baluteshih Holiday (IOI14_holiday) C++14
100 / 100
 747 ms 43604 KB 
#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+(ll)(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));
}

Compilation message

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;
        ~^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3948 KB Output is correct
2 Correct 19 ms 3952 KB Output is correct
3 Correct 24 ms 6388 KB Output is correct
4 Correct 25 ms 6256 KB Output is correct
5 Correct 68 ms 18160 KB Output is correct
6 Correct 24 ms 6008 KB Output is correct
7 Correct 39 ms 10356 KB Output is correct
8 Correct 46 ms 12404 KB Output is correct
9 Correct 17 ms 4344 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1272 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 12 ms 1272 KB Output is correct
5 Correct 11 ms 1180 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 3 ms 508 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3952 KB Output is correct
2 Correct 166 ms 43180 KB Output is correct
3 Correct 146 ms 18448 KB Output is correct
4 Correct 9 ms 1144 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 738 ms 43512 KB Output is correct
9 Correct 747 ms 43604 KB Output is correct