oj.uz

Submission #1106531

# Submission time Handle Problem Language Result Execution time Memory
1106531 2024-10-30T14:58:58 Z Octagons Mosaic (IOI24_mosaic) C++17
12 / 100
 192 ms 34516 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+2, lim = 3;
int n, q, a[lim][N], b[N][lim], ar[220][220];
vector<int> v, v2;
ll pref[N], pref2[N];
ll geta(int rw, int l, int r) {
	return a[rw][r] - (l ? a[rw][l-1] : 0);
}
 
ll getb(int col, int l, int r) {
	l = max(l, lim-1);
	if (l > r)return 0;
	return b[r][col] - b[l-1][col];
}
 
ll getp(int l, int r) {
	return pref[r] - (l ? pref[l-1] : 0ll);
}
 
ll getp2(int l, int r) {
	return pref2[r] - (l ? pref2[l-1] : 0ll);
}
 
ll get(int x, int y) {
	if (x < 0 || y < 0)return 0;
	ll ret = 0;
	for (int i = 0; i+1 < lim && i <= x; i++) {
		ret += geta(i, 0, y);
	}
	for (int i = 0; i+1 < lim && i <= y; i++) {
		ret += getb(i, 0, x);
	}
	if (x+1 < lim || y+1 < lim)return ret;
	x -= (lim - 1), y -= (lim - 1);
	int id = upper_bound(v.begin(), v.end(), y+1) - v.begin();
	if (id) {
		--id;
		int id2 = upper_bound(v.begin(), v.end(), y-x) - v.begin();
		--id2;
		id2 = min(id2, id);
		if (id2 == -1) {
			ret += ll(id+1) * ll(y+1) - getp(0, id);
		} else {
			ret += ll(id2+1) * ll(x+1);
			if (id2 != id)ret += ll(id-id2) * ll(y+1) - getp(id2+1, id);
		}
	}
	swap(x, y);
	id = upper_bound(v2.begin(), v2.end(), y+1) - v2.begin();
	if (id) {
		--id;
		int id2 = upper_bound(v2.begin(), v2.end(), y-x) - v2.begin();
		--id2;
		id2 = min(id2, id);
		if (id2 == -1) {
			ret += ll(id+1) * ll(y+1) - getp2(0, id);
		} else {
			ret += ll(id2+1) * ll(x+1);
			if (id2 != id)ret += ll(id-id2) * ll(y+1) - getp2(id2+1, id);
		}
	}
	return ret;
}
 
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
	q = L.size();
	n = X.size();
	v.clear();
	v2.clear();
	vector<long long> ret(q);
	for (int i = 0; i < n; i++) {
		a[0][i] = X[i];
		b[i][0] = Y[i];
		if (i < lim) {
			b[0][i] = X[i];
			a[i][0] = Y[i];
		}
		ar[0][i] = X[i];
		ar[i][0] = Y[i];
	}
	for (int i = 1; i < lim; i++) {
		for (int j = 1; j < n; j++) {
			a[i][j] = (a[i-1][j] || a[i][j-1] ? 0 : 1);
		}
	}
	for (int i = 0; i < lim; i++) {
		for (int j = 1; j < n; j++) {
			if (i == lim-1) {
				continue;
			}
			a[i][j] += a[i][j-1];
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < lim; j++) {
			b[i][j] = (b[i-1][j] || b[i][j-1] ? 0 : 1);
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < lim; j++) {
			if (j == lim-1) {
				continue;
			}
			b[i][j] += b[i-1][j];
		}
	}
	for (int i = lim-1; i < n; i++) {
		if (a[lim-1][i]) {
			v.push_back(i - (lim - 1));
		}
	}
	for (int j = lim; j < n; j++) {
		if (b[j][lim-1]) {
			v2.push_back(j - (lim - 1));
		}
	}
	ll sm = 0;
	for (int i = 0; i < v.size(); i++) {
		sm += ll(v[i]);
		pref[i] = sm;
	}
	sm = 0;
	for (int i = 0; i < v2.size(); i++) {
		sm += ll(v2[i]);
		pref2[i] = sm;
	}
	for (int i = 0; i < q; i++) {
		int x = T[i], y = L[i];
		int x2 = B[i], y2 = R[i];
		ret[i] = get(x2, y2) - get(x-1, y2) - get(x2, y-1) + get(x-1, y-1);
	}
	return ret;
}

Compilation message

mosaic.cpp: In function 'std::vector<long long int> mosaic(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
mosaic.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
mosaic.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |  for (int i = 0; i < v2.size(); i++) {
      |                  ~~^~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 6480 KB Output is correct
12 Correct 1 ms 6480 KB Output is correct
13 Correct 1 ms 6480 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 1 ms 6480 KB Output is correct
16 Correct 1 ms 6480 KB Output is correct
17 Correct 2 ms 6652 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 34388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 6480 KB Output is correct
12 Correct 1 ms 6480 KB Output is correct
13 Correct 1 ms 6480 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 1 ms 6480 KB Output is correct
16 Correct 1 ms 6480 KB Output is correct
17 Correct 2 ms 6652 KB Output is correct
18 Incorrect 192 ms 15656 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 14408 KB Output is correct
2 Runtime error 92 ms 34384 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 109 ms 34516 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 34388 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 1 ms 4432 KB Output is correct
11 Correct 1 ms 4432 KB Output is correct
12 Correct 1 ms 6480 KB Output is correct
13 Correct 1 ms 6480 KB Output is correct
14 Correct 1 ms 6480 KB Output is correct
15 Correct 1 ms 6480 KB Output is correct
16 Correct 1 ms 6480 KB Output is correct
17 Correct 1 ms 6480 KB Output is correct
18 Correct 2 ms 6652 KB Output is correct
19 Runtime error 83 ms 34388 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -