Submission #671138

#	Time	Username	Problem	Language	Result	Execution time	Memory
671138		qin	Pyramid Base (IOI08_pyramid_base)	C++14	70 / 100	5083 ms	96352 KiB

pyramid_base

#include <bits/stdc++.h>
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
using namespace std;
typedef unsigned ll;
int base = 1;
ll inf = 4e09;
struct event{
		int y1, y2; ll c;
		event(){}
		event(int y1, int y2, ll c) : y1(y1), y2(y2), c(c){}
};
struct seg{
		vector<ll> t, p;
		void init(int n){
				while(base < n) base<<=1;
				t.resize(base<<1|1);
				p.resize(base<<1|1);
		} void purge(){for(int i = 1; i <= base<<1; ++i) t[i] = p[i] = 0;};
		void add(int i, ll ile){t[i] += ile, p[i] += ile;}
		void push(int i){
				add(i<<1, p[i]);
				add(i<<1|1, p[i]);
				p[i] = 0;
		} void update(int i, int pocz, int kon, int x, int y, ll w){
				if(x <= pocz && kon <= y) return void(add(i, w));
				push(i);
				int sr = (pocz+kon) >> 1;
				if(x <= sr) update(i<<1, pocz, sr, x, y, w);
				if(sr < y) update(i<<1|1, sr+1, kon, x, y, w);
				t[i] = MIN(t[i<<1], t[i<<1|1]);
		}
} seg;

bool zamiatanie(int n, int m, int y, ll w, vector<vector<event>>& p, vector<vector<event>>& k){
		seg.purge();
		if(1 < y) seg.update(1, 1, base, 1, y-1, inf);
		if(m < base) seg.update(1, 1, base, m+1, base, inf);
		int pc, kn;
		for(int i = 1; i <= y; ++i)
				for(event u : p[i]){
						pc = MAX(y, u.y1), kn = MIN(m, u.y2+y-1);
						//if(pc <= kn) 
						seg.update(1, 1, base, pc, kn, u.c);
				}
		
				
		ll wynik = seg.t[1];
		for(int i = y+1; i <= n; ++i){
				for(event u : p[i]){
						pc = MAX(y, u.y1), kn = MIN(m, u.y2+y-1);
						//if(pc <= kn) 
						seg.update(1, 1, base, pc, kn, u.c);
				}
				for(event u : k[i-y]){
						pc = MAX(y, u.y1), kn = MIN(m, u.y2+y-1);
						//if(pc <= kn) 
						seg.update(1, 1, base, pc, kn, -u.c);
				}
				wynik = MIN(wynik, seg.t[1]);
		}
		
		if(w < wynik) return 0;
		else return 1;
}

int main(){
		int n, m, w, q, x1, y1, x2, y2, c;
		scanf("%d%d%d%d", &n, &m, &w, &q);
		vector<vector<event>> p(n+1), k(n+1);
		seg.init(m);
		for(int i = q+1; --i; ){
				scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
				p[x1].emplace_back(y1, y2, c);
				k[x2].emplace_back(y1, y2, c);
		} int pocz = 1, kon = MIN(n, m), y;
		bool b = zamiatanie(n, m, 1, w, p, k);
		if(!b){printf("0\n"); return 0;}
		while(pocz != kon){
				y = ((pocz + kon) >> 1) + 1; // y to nasz sr w binserczu
				b = zamiatanie(n, m, y, w, p, k);
				if(!b) kon = y - 1;
				else pocz = y;
		}
		printf("%d\n", pocz);
		
		return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d%d%d%d", &n, &m, &w, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10