oj.uz

답안 #73822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73822 2018-08-29T05:32:17 Z 아인따(#2278) 놀이터에 떨어진 이상한 약 (FXCUP3_gorgeous) C++11
0 / 100
 4 ms 520 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define pii pair<int,int>
#define N_ 301000
#define SZ 524288
using namespace std;
struct point {
	int b, e, c, ck;
	bool operator <(const point &p)const {
		return b != p.b ? b<p.b : e>p.e;
	}
}P[N_*3];
int w[N_], cnt, C[N_];
int n;
long long IT[SZ + SZ], D[N_*3], Res[N_];
void Put(int a, long long  b) {
	a += SZ;
	while (a) {
		IT[a] = max(IT[a], b);
		a >>= 1;
	}
}
long long Max(int b, int e) {
	long long r = 0;
	b += SZ, e += SZ;
	while (b <= e) {
		r = max(r, max(IT[b], IT[e]));
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
void Calc(int a) {
	int b = P[a].b, e = P[a].e;
	D[a] = Max(e, n) + P[a].c;
}
int main() {
	int i;
	scanf("%d", &n);
	P[cnt++] = { 1,n,0 };
	for (i = 1; i <= n; i++) scanf("%d", &w[i]);
	for (i = 1; i <= n; i++){
		scanf("%d", &C[i]);
		if (i - w[i] + 1 >= 1)P[cnt++] = { i - w[i] + 1, i, C[i], 1 };
		if (i + w[i] - 1 <= n)P[cnt++] = { i, i + w[i] - 1, C[i], 0 };
		if(w[i] != 1)P[cnt++] = { i,i,0,0 };
	}
	sort(P, P + cnt);
	vector<pii>V;
	for (i = 0; i < cnt; i++) {
		if (i && P[i].b != P[i - 1].b) {
			for (auto &x : V) Put(x.first, x.second);
			V.clear();
		}
		Calc(i);
		if (P[i].ck == 1)Put(P[i].e - 1, D[i]);
		else V.push_back({ P[i].e, D[i] });
	}
	for (i = 0; i < cnt; i++) {
		if (P[i].b == P[i].e)Res[P[i].b] = max(Res[P[i].b], D[i]);
	}
	for (i = 1; i <= n; i++)printf("%lld ", Res[i]);
}

Compilation message

gorgeous.cpp: In function 'void Calc(int)':
gorgeous.cpp:34:6: warning: unused variable 'b' [-Wunused-variable]
  int b = P[a].b, e = P[a].e;
      ^
gorgeous.cpp: In function 'int main()':
gorgeous.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
gorgeous.cpp:41:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++) scanf("%d", &w[i]);
                           ~~~~~^~~~~~~~~~~~~
gorgeous.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &C[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 3 ms 520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 3 ms 520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Incorrect 3 ms 520 KB Output isn't correct
4 Halted 0 ms 0 KB -