oj.uz

답안 #54027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54027 2018-07-02T08:34:47 Z khsoo01 Pyramid Base (IOI08_pyramid_base) C++11
70 / 100
 5000 ms 37688 KB 
#include<bits/stdc++.h>
using namespace std;

const int O = 400005, N = 1000005, inf = 2e9+7;

int n, m, b, o;

struct obstacle {
	int xs, ys, xe, ye, v;
} a[O];

struct event {
	int s, e, x, v;
	bool operator < (event &T) {
		return x < T.x;
	}
};

vector<event> ev;

struct segtree {
	int l[4*N], v[4*N];
	void lazydown (int P) {
		v[2*P] += l[P];
		v[2*P+1] += l[P];
		l[2*P] += l[P];
		l[2*P+1] += l[P];
		l[P] = 0;
	}
	void upd (int S, int E, int V, int P = 1, int SS = 1, int SE = m) {
		if(S <= SS && SE <= E) {
			v[P] += V;
			l[P] += V;
			return;
		}
		if(E < SS || SE < S) return;
		lazydown(P);
		int M = (SS+SE)/2;
		upd(S, E, V, 2*P, SS, M);
		upd(S, E, V, 2*P+1, M+1, SE);
		v[P] = min(v[2*P], v[2*P+1]);
	}
	int get (int S, int E, int P = 1, int SS = 1, int SE = m) {
		if(S <= SS && SE <= E) return v[P];
		if(E < SS || SE < S) return inf;
		lazydown(P);
		int M = (SS+SE)/2;
		return min(get(S, E, 2*P, SS, M), get(S, E, 2*P+1, M+1, SE));
	}
} seg;

bool can (int P) {
	ev.clear();
	for(int i=1;i<=o;i++) {
		ev.push_back({max(1, a[i].ys-P+1), a[i].ye, max(1, a[i].xs-P+1), a[i].v});
		ev.push_back({max(1, a[i].ys-P+1), a[i].ye, a[i].xe+1, -a[i].v});
	}
	sort(ev.begin(), ev.end());
	if(ev[0].x > 1) return true;
	int mn = inf;
	for(int i=0;i<(int)ev.size();i++) {
		seg.upd(ev[i].s, ev[i].e, ev[i].v);
		if((i+1 == (int)ev.size() || ev[i].x != ev[i+1].x) && ev[i].x <= n-P+1) {
			mn = min(mn, seg.get(1, m-P+1));
		}
	}
	return mn <= b;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&b,&o);
	for(int i=1;i<=o;i++) {
		scanf("%d%d%d%d%d",&a[i].xs,&a[i].ys,&a[i].xe,&a[i].ye,&a[i].v);
	}
	int S = 0, E = min(n, m);
	while(S<E) {
		int M = (S+E)/2;
		can(M+1) ? S = M+1 : E = M;
	}
	printf("%d\n",S);
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d",&n,&m,&b,&o);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d",&a[i].xs,&a[i].ys,&a[i].xe,&a[i].ye,&a[i].v);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 356 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 392 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 952 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 2572 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 10564 KB Output is correct
2 Correct 46 ms 16476 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 16716 KB Output is correct
2 Correct 45 ms 16716 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 16716 KB Output is correct
2 Correct 84 ms 16716 KB Output is correct
3 Correct 69 ms 16716 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 16716 KB Output is correct
2 Correct 422 ms 16716 KB Output is correct
3 Correct 390 ms 16716 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 758 ms 18076 KB Output is correct
2 Correct 65 ms 18076 KB Output is correct
3 Correct 298 ms 18304 KB Output is correct
4 Correct 966 ms 18304 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1031 ms 18472 KB Output is correct
2 Correct 1059 ms 18472 KB Output is correct
3 Correct 688 ms 18472 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1265 ms 18608 KB Output is correct
2 Correct 1464 ms 18608 KB Output is correct
3 Correct 1798 ms 18608 KB Output is correct
4 Correct 1581 ms 18608 KB Output is correct
5 Correct 1480 ms 18640 KB Output is correct
6 Correct 1018 ms 18644 KB Output is correct

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5029 ms 27324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5020 ms 32436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5008 ms 37688 KB Time limit exceeded
2 Halted 0 ms 0 KB -