oj.uz

Submission #54023

# Submission time Handle Problem Language Result Execution time Memory
54023 2018-07-02T08:31:36 Z khsoo01 Pyramid Base (IOI08_pyramid_base) C++11
39 / 100
 2348 ms 66916 KB 
#include<bits/stdc++.h>
using namespace std;

const int O = 400005, 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*O], v[4*O];
	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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 536 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 740 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2564 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 10192 KB Output is correct
2 Incorrect 51 ms 14552 KB Output isn't correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 14572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14572 KB Output is correct
2 Correct 74 ms 14572 KB Output is correct
3 Correct 77 ms 14572 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 14572 KB Output is correct
2 Correct 552 ms 14572 KB Output is correct
3 Correct 327 ms 14572 KB Output is correct

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 780 ms 15836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 933 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1202 ms 16088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 581 ms 46424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1392 ms 56736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2348 ms 66916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -