oj.uz

Submission #39669

# Submission time Handle Problem Language Result Execution time Memory
39669 2018-01-17T03:37:43 Z farmersrice Nuclearia (CEOI15_nuclearia) C++14
15 / 100
 1000 ms 241096 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#pragma GCC target ("avx,tune=native")
//Use above if bruteforcing with lots of small operations. Or just use it anytime, there's no downside. AVX is better slightly
/*
TASK: hidden
LANG: C++11
*/
using namespace std;
typedef long long ll;
typedef pair<int, int> pair2;
typedef pair<int, pair<int, int> > pair3;
typedef pair<int, pair<int, pair<int, int> > > pair4;
#define MAXN 200013
#define INF 1000000000000000000LL
#define mp make_pair
#define add push_back
#define remove pop

//only works for H = 1 case

int n;
int w, h, q;
int x[MAXN], y[MAXN];
ll a[MAXN], b[MAXN];

//copy from radoslav11 coding library

ll sum[4 * 2500013];
ll lazy[4 * 2500013];
ll lazy_ap[4 * 2500013];

struct segment_tree_ap {
	//node_ap tr[4 * 2500013];

	void update(int l, int r, int idx) {
		if (lazy[idx]) {
			sum[idx] += (r - l + 1) * lazy[idx];

			if (l != r) {
				lazy[2 * idx] += lazy[idx];
				lazy[2 * idx + 1] += lazy[idx];
			}

			lazy[idx] = 0;
		}	

		if (lazy_ap[idx]) {
			int mid = (l + r) >> 1;
			sum[idx] += (((ll)(r - l + 1)) * (r - l + 2) / 2) * lazy_ap[idx];

			if(l != r) {
				lazy_ap[2 * idx] += lazy_ap[idx];
				lazy_ap[2 * idx + 1] += lazy_ap[idx];
				lazy[2 * idx + 1] += lazy_ap[idx] * (mid - l + 1);
			}

			lazy_ap[idx] = 0;
		}
	}
	
	void update(int qL, int qR, ll val, ll prog, int l, int r, int idx) {
		update(l, r, idx);

		if (qL > r || l > qR)
			return;

		if (qL <= l && r <= qR) {
			lazy[idx] += val + (l - qL) * prog;
			lazy_ap[idx] += prog;
			update(l, r, idx);
			return;
		}

		int mid = (l + r) >> 1;
		update(qL, qR, val, prog, l, mid, 2 * idx);
		update(qL, qR, val, prog, mid + 1, r, 2 * idx + 1);

		sum[idx] = sum[2 * idx] + sum[2 * idx + 1];
	}

	ll query(int qL, int qR, int l, int r, int idx) {
		update(l, r, idx);

		if(l > qR || r < qL)
			return 0;

		if(qL <= l && r <= qR)
			return sum[idx];

		int mid = (l + r) >> 1;
		return query(qL, qR, l, mid, 2 * idx) + query(qL, qR, mid + 1, r, 2 * idx + 1);
	}
};
segment_tree_ap t;

int main() {
	//ios_base::sync_with_stdio(false); 
	//cin.tie(NULL);

	scanf("%d%d", &w, &h);
	scanf("%d", &n);
	//cin >> w >> h;
	//assert(h == 1);
	//cin >> n;

	for (int i = 0; i < n; i++) {
		//cin >> x[i] >> y[i] >> a[i] >> b[i];
		scanf("%d%d%lld%lld", &x[i], &y[i], &a[i], &b[i]);
	}

	for (int i = 0; i < n; i++) {
		ll possible = (a[i] - 1) / b[i];

		if (possible == 0) {
			t.update(x[i], x[i], a[i], 0, 0, w + 1, 1);
			continue;
		}

		int start = max(1, (int) (x[i] - possible));
		int end = min(w, (int) (x[i] + possible));

		//cout << "plant " << i << " found start, end " << start << ' ' << end
		//<< endl;

		ll startval = a[i] - ((x[i] - (ll)start) * b[i]);
		//cout << "startval is " << startval << endl;

		t.update(start, x[i], startval - b[i], b[i], 0, w + 1, 1);
		if (x[i] + 1 <= end) t.update(x[i] + 1, end, a[i], -b[i], 0, w + 1, 1);
	}

	scanf("%d", &q);//cin >> q;
	for (int i = 0; i < q; i++) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);//cin >> x1 >> y1 >> x2 >> y2;

		//cout << "boudns are " <<  x1 << ' ' << x2 << endl;
		ll sum = t.query(x1, x2, 0, w + 1, 1);

		ll cells = x2 - x1 + 1;

		//cout << "query " << i << " found sum " << sum << " cells " << cells << endl;

		ll remainder = sum % cells;
		if ((cells % 2 == 0 && remainder >= cells / 2) || (cells % 2 == 1 && remainder > cells / 2)) {
			printf("%lld\n", 1 + sum / cells);//cout << 1 + sum / cells << endl; 
		} else {
			printf("%lld\n", sum / cells);//cout << sum / cells << endl;
		}
	}
	return 0;
}

Compilation message

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:102:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &w, &h);
                       ^
nuclearia.cpp:103:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
nuclearia.cpp:110:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%lld%lld", &x[i], &y[i], &a[i], &b[i]);
                                                    ^
nuclearia.cpp:134:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);//cin >> q;
                 ^
nuclearia.cpp:137:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &x1, &y1, &x2, &y2);//cin >> x1 >> y1 >> x2 >> y2;
                                        ^

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 241096 KB Output is correct
2 Correct 156 ms 241096 KB Output is correct
3 Correct 96 ms 241096 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 241096 KB Output is correct
2 Correct 149 ms 241096 KB Output is correct

Subtask #3
0 / 3.0

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

Subtask #4
0 / 2.0

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

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 241096 KB Output is correct
2 Correct 159 ms 241096 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 241096 KB Output is correct
2 Correct 156 ms 241096 KB Output is correct

Subtask #7
0 / 6.0

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

Subtask #8
0 / 4.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 241096 KB Execution timed out

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 241096 KB Execution timed out

Subtask #11
0 / 15.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 12.0

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

Subtask #14
0 / 8.0

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