Submission #54023

#	Time	Username	Problem	Language	Result	Execution time	Memory
54023		khsoo01	Pyramid Base (IOI08_pyramid_base)	C++11	39 / 100	2348 ms	66916 KiB

pyramid_base

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10