Submission #70752

#	Time	Username	Problem	Language	Result	Execution time	Memory
70752		imsifile	Gorgeous Pill (FXCUP3_gorgeous)	C++98	100 / 100	444 ms	22316 KiB

gorgeous

#include<stdio.h>
#include<algorithm>
using namespace std;

typedef long long lld;

struct garo {
	int x, y; lld v; // (x,y) -> (x+1,y)
	garo(int x_=0, int y_=0, lld v_=0){ x=x_, y=y_, v=v_; }
	bool operator< (const garo& c) const {
		if(x != c.x) return x<c.x;
		return y>c.y;
	}
} gs[303030];

struct sero {
	int x, y; lld v; // (x,y) -> (x,y+1)
	sero(int x_=0, int y_=0, lld v_=0){ x=x_, y=y_, v=v_; }
	bool operator< (const sero& c) const {
		if(x != c.x) return x<c.x;
		return y<c.y;
	}
} ss[303030];

int N, ba[303030], j2; lld dap[303030], itr[1<<20];

lld getdy(int ix){
	int s=j2, e=j2+ix;
	lld mx=0;
	while(1){
		if(s%2) mx = max(mx, itr[s]), s++;
		if(e%2==0) mx = max(mx, itr[e]), e--;
		if(s>e) break;
		s>>=1, e>>=1;
	}
	return mx;
}

void update(int ix, lld v){
	for(ix+=j2; ix; ix>>=1) itr[ix] = max(itr[ix], v);
}

int main(){
	scanf("%d", &N);
	for(j2=1; j2<=N; j2<<=1);
	for(int i=0; i<N; i++) scanf("%d", &ba[i]);
	for(int i=0; i<N; i++){
		lld dmg; scanf("%lld", &dmg);
		gs[i]=garo(N-i-1, i+1-ba[i], dmg);
		ss[i]=sero(N-i-ba[i], i, dmg);
		if(ba[i]==1) dap[i]+=dmg;
	}
	sort(gs, gs+N); sort(ss, ss+N);
	for(int i=0, g=0, s=0; i<N; i++){
		for(; s<N; s++){
			if(ss[s].x < i) continue;
			if(ss[s].x > i) break;
			update(ss[s].y+1, ss[s].v+getdy(ss[s].y));
		}
		dap[N-1-i] += getdy(N-1-i);
		for(; g<N; g++){
			if(gs[g].x < i) continue;
			if(gs[g].x > i) break;
			if(gs[g].y < 0) continue;
			update(gs[g].y, gs[g].v+getdy(gs[g].y));
		}
	}
	for(int i=0; i<N; i++) printf("%lld ", dap[i]);
	return 0;
}

Compilation message (stderr)

gorgeous.cpp: In function 'int main()':
gorgeous.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
gorgeous.cpp:46:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%d", &ba[i]);
                         ~~~~~^~~~~~~~~~~~~~
gorgeous.cpp:48:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   lld dmg; scanf("%lld", &dmg);
            ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 39 / 39
• Subtask 3: 49 / 49