oj.uz

Submission #70752

# Submission time Handle Problem Language Result Execution time Memory
70752 2018-08-23T09:48:36 Z imsifile Gorgeous Pill (FXCUP3_gorgeous) C++
100 / 100
 444 ms 22316 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9872 KB Output is correct
2 Correct 10 ms 9872 KB Output is correct
3 Correct 11 ms 9888 KB Output is correct
4 Correct 11 ms 9932 KB Output is correct
5 Correct 10 ms 10008 KB Output is correct
6 Correct 11 ms 10016 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9872 KB Output is correct
2 Correct 10 ms 9872 KB Output is correct
3 Correct 11 ms 9888 KB Output is correct
4 Correct 11 ms 9932 KB Output is correct
5 Correct 10 ms 10008 KB Output is correct
6 Correct 11 ms 10016 KB Output is correct
7 Correct 11 ms 10016 KB Output is correct
8 Correct 10 ms 10016 KB Output is correct
9 Correct 11 ms 10016 KB Output is correct
10 Correct 9 ms 10016 KB Output is correct
11 Correct 11 ms 10020 KB Output is correct
12 Correct 13 ms 10032 KB Output is correct
13 Correct 10 ms 10036 KB Output is correct
14 Correct 11 ms 10064 KB Output is correct
15 Correct 10 ms 10064 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9872 KB Output is correct
2 Correct 10 ms 9872 KB Output is correct
3 Correct 11 ms 9888 KB Output is correct
4 Correct 11 ms 9932 KB Output is correct
5 Correct 10 ms 10008 KB Output is correct
6 Correct 11 ms 10016 KB Output is correct
7 Correct 11 ms 10016 KB Output is correct
8 Correct 10 ms 10016 KB Output is correct
9 Correct 11 ms 10016 KB Output is correct
10 Correct 9 ms 10016 KB Output is correct
11 Correct 11 ms 10020 KB Output is correct
12 Correct 13 ms 10032 KB Output is correct
13 Correct 10 ms 10036 KB Output is correct
14 Correct 11 ms 10064 KB Output is correct
15 Correct 10 ms 10064 KB Output is correct
16 Correct 18 ms 10192 KB Output is correct
17 Correct 28 ms 11024 KB Output is correct
18 Correct 91 ms 13904 KB Output is correct
19 Correct 123 ms 15048 KB Output is correct
20 Correct 363 ms 21628 KB Output is correct
21 Correct 444 ms 22272 KB Output is correct
22 Correct 363 ms 22272 KB Output is correct
23 Correct 364 ms 22316 KB Output is correct
24 Correct 307 ms 22316 KB Output is correct
25 Correct 258 ms 22316 KB Output is correct