oj.uz

Submission #671138

# Submission time Handle Problem Language Result Execution time Memory
671138 2022-12-12T07:24:12 Z qin Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 96352 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1108 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7124 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 63724 KB Output is correct
2 Correct 36 ms 63672 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 63784 KB Output is correct
2 Correct 158 ms 63692 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1364 KB Output is correct
2 Correct 52 ms 1400 KB Output is correct
3 Correct 45 ms 1484 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 8276 KB Output is correct
2 Correct 262 ms 8248 KB Output is correct
3 Correct 241 ms 8232 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 65472 KB Output is correct
2 Correct 121 ms 48932 KB Output is correct
3 Correct 141 ms 17876 KB Output is correct
4 Correct 772 ms 65556 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 65960 KB Output is correct
2 Correct 908 ms 65868 KB Output is correct
3 Correct 466 ms 65996 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 66404 KB Output is correct
2 Correct 1085 ms 66292 KB Output is correct
3 Correct 1099 ms 66256 KB Output is correct
4 Correct 1087 ms 66272 KB Output is correct
5 Correct 1069 ms 66380 KB Output is correct
6 Correct 463 ms 66540 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5083 ms 80972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5035 ms 88780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5078 ms 96352 KB Time limit exceeded
2 Halted 0 ms 0 KB -