Submission #96497

#	Time	Username	Problem	Language	Result	Execution time	Memory
96497		Retro3014	Gorgeous Pill (FXCUP3_gorgeous)	C++14	100 / 100	551 ms	55940 KiB

gorgeous

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 300000
typedef long long ll;
int N;
vector<int> C, D;
struct SEG{
	SEG (int l, int r, ll mx) : l(l), r(r), mx(mx) {}
	int l, r;
	ll mx;
};
vector<SEG> seg;

void init(){
	seg.push_back({-1, -1, 0});
}

void update(int idx, int s, int e, int x, ll y){
	seg[idx].mx = max(seg[idx].mx, y);
	if(s==e)	return;
	if(x<=(s+e)/2){
		if(seg[idx].l==-1){
			seg[idx].l = seg.size(); seg.push_back({-1, -1, 0});
		}update(seg[idx].l, s, (s+e)/2, x, y);
	}else{
		if(seg[idx].r==-1){
			seg[idx].r = seg.size(); seg.push_back({-1, -1, 0});
		}update(seg[idx].r, (s+e)/2+1, e, x, y);
	}
	return;
}

ll max(int idx, int s, int e, int x, int y){
	if(idx==-1)	return 0;
	if(x<=s && e<=y)	return seg[idx].mx;
	if(x>e || y<s)	return 0;
	return max(max(seg[idx].l, s, (s+e)/2, x, y), max(seg[idx].r, (s+e)/2+1, e, x, y));
}


struct S{
	S(int x, int y, int idx1, int idx2, int type) : x(x), y(y), idx1(idx1), idx2(idx2), type(type) {}
	int x, y;
	int idx1, idx2;
	int type;
	bool operator <(const S &a)const{
		if(y==a.y){
			if(x==a.x){
				return type<a.type;
			}
			return x>a.x;
		}return y<a.y;
	}
};
vector<S> v;

ll ans[MAX_N+1];
ll cost[MAX_N+1][2];

int main(){
	init();
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		int a;
		scanf("%d", &a); C.push_back(a);
	}
	for(int i=0; i<N; i++){
		int a; scanf("%d", &a); D.push_back(a);
	}
	for(int i=0; i<N; i++){
		v.push_back({i, i, i, i, -1});
		if(C[i]==1)	continue;
		if(i+C[i]-1 < N){
			v.push_back({i, i+C[i]-1, i, 0, 1});
			v.push_back({i+1, i+C[i]-1, i, 0, 2});
		}
		if(i-C[i]+1 >= 0){
			v.push_back({i-C[i]+1, i, i, 1, 1});
			v.push_back({i-C[i]+1, i-1, i, 1, 2});
		}
	}
	sort(v.begin(), v.end());
	while(!v.empty()){
		S now = v.back(); v.pop_back();
		//cout<<now.x<<' '<<now.y<<' '<<now.idx1<<' '<<now.idx2<<' '<<now.type<<endl;
		if(now.type==-1){
			ans[now.idx1] = max(0, 0, N-1, 0, now.x);
		}else if(now.type==1){
			cost[now.idx1][now.idx2] = max(0, 0, N-1, 0, now.x) + (ll)D[now.idx1];
		}else if(now.type==2){
			update(0, 0, N-1, now.x, cost[now.idx1][now.idx2]);
		}
	}
	for(int i=0; i<N; i++){
		if(C[i]==1)	ans[i]+=(ll)D[i];
		printf("%lld ", ans[i]);
	}
	return 0;
}

Compilation message (stderr)

gorgeous.cpp: In function 'int main()':
gorgeous.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
gorgeous.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a); C.push_back(a);
   ~~~~~^~~~~~~~~~
gorgeous.cpp:73:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a); D.push_back(a);
          ~~~~~^~~~~~~~~~

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