oj.uz

Submission #516138

# Submission time Handle Problem Language Result Execution time Memory
516138 2022-01-20T12:38:28 Z mosiashvililuka Holiday (IOI14_holiday) C++14
100 / 100
 573 ms 23796 KB 
#include"holiday.h"
//#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[300009],D,pas,jm,n,g[300009],LF[300009][3],RG[300009][3],RR,za,T[300009],l,r,z,zz,k,seg[300009],seg2[300009],K;
map <int, int> M;
map <int, int>::iterator IT;
void upd(int q, int w, int rr){
	q=za+q-1;
	while(q!=0){
		seg[q]+=w;seg2[q]+=rr;
		q/=2;
	}
}
void wv(){
	za=1;
	while(za<a) za*=2;
	for(i=0; i<=za*2; i++){
		seg[i]=seg2[i]=0;
	}
	for(i=0; i<=za; i++) T[i]=0;
	M.clear();
	for(i=1; i<=a; i++) M[f[i]]=1;
	zx=0;
	for(IT=M.begin(); IT!=M.end(); IT++){
		zx++;M[(*IT).first]=zx;T[zx]=(*IT).first;
	}
	for(i=1; i<=a; i++) f[i]=M[f[i]];
	//
	upd(f[1],1,T[f[1]]);K=1;
}
void Moveto(int q){
	while(K<q){
		K++;upd(f[K],1,T[f[K]]);
	}
	while(K>q){
		upd(f[K],-1,-T[f[K]]);K--;
	}
}
void read(int q, int w, int rr){
	if(q>w||k<=0) return;
	if(seg[rr]<=k){
		k-=seg[rr];
		z+=seg2[rr];
		return;
	}
	if(q==w){
		z+=T[q]*k;
		k=0;
		return;
	}
	read((q+w)/2+1,w,rr*2+1);
	read(q,(q+w)/2,rr*2);
}
void rec(int q, int w, int qq, int ww){
	if(q>w) return;
	int mid=(q+w)/2,we=0;
	long long qw=0;
	for(int h=qq; h<=ww; h++){
		Moveto(h);
		k=mid-(h-1)*RR;z=0;
		if(k<=0) break;
		read(1,za,1);
		if(qw<z){
			qw=z;we=h;
		}
	}
	LF[mid][RR]=qw;
	rec(q,mid-1,qq,we);
	rec(mid+1,w,we,ww);
}
long long int findMaxAttraction(int Nn, int start, int Dd, int attraction[]) {
	n=Nn;start++;D=Dd;a=n;
	for(i=1; i<=n; i++){
		g[i]=attraction[i-1];f[i]=g[i];
	}
	for(i=start; i<=n; i++){
		f[i-start+1]=g[i];
	}
	a=n-start+1;RR=1;
	wv();
	rec(1,D,1,a);
	RR=2;
	rec(1,D,1,a);
	for(i=1; i<=D; i++){
		RG[i][1]=LF[i][1];RG[i][2]=LF[i][2];
		LF[i][1]=LF[i][2]=0;
	}
	if(start!=1){
	for(i=start-1; i>=1; i--){
		f[start-1-i+1]=g[i];
	}
	a=start-1;RR=1;
	wv();
	rec(1,D,1,a);
	RR=2;
	rec(1,D,1,a);
	}
	//
	if(start==1) return RG[D][1];
	pas=max(pas,RG[D][1]);
	for(i=0; i<=D; i++){
		if(D-i-2>=0){
			zx=LF[i][2]+RG[D-i-2][1];
			pas=max(pas,zx);
		}
		if(D-i-1>=0){
			zx=RG[i][2]+LF[D-i-1][1];
			pas=max(pas,zx);
		}
	}
	return pas;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 16716 KB Output is correct
2 Correct 451 ms 16884 KB Output is correct
3 Correct 555 ms 16956 KB Output is correct
4 Correct 466 ms 16960 KB Output is correct
5 Correct 384 ms 13520 KB Output is correct
6 Correct 132 ms 11068 KB Output is correct
7 Correct 209 ms 8236 KB Output is correct
8 Correct 246 ms 8256 KB Output is correct
9 Correct 100 ms 13476 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1356 KB Output is correct
2 Correct 9 ms 1292 KB Output is correct
3 Correct 8 ms 1356 KB Output is correct
4 Correct 9 ms 1100 KB Output is correct
5 Correct 8 ms 1100 KB Output is correct
6 Correct 2 ms 844 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 19116 KB Output is correct
2 Correct 573 ms 23796 KB Output is correct
3 Correct 79 ms 5088 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 402 ms 10072 KB Output is correct
9 Correct 469 ms 10060 KB Output is correct