oj.uz

Submission #568888

# Submission time Handle Problem Language Result Execution time Memory
568888 2022-05-26T10:04:47 Z nonsensenonsense1 Fish 2 (JOI22_fish2) C++17
0 / 100
 87 ms 4436 KB 
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>

const int N = 100005;
int n, q, a[N], le[N], ri[N], cnt[N];
std::pair<int, int> b[N], b1[N];
bool u[N];
long long sum[N];
int c[(1 << 16) + 1];

void countsort(int len) {
	for (int t = 1; t >= 0; --t) {
		memset(c, 0, sizeof c);
		for (int i = 0; i < len; ++i) ++c[(b[i].first >> t * 16 & 65535) + 1];
		for (int i = 1; i < 65536; ++i) c[i] += c[i - 1];
		for (int i = 0; i < len; ++i) b1[c[b[i].first >> t * 16 & 65535]++] = b[i];
		std::swap(b, b1);
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	scanf("%d", &q);
	while (q--) {
		int t;
		scanf("%d", &t);
		if (t == 1) {
			int x, y;
			scanf("%d%d", &x, &y);
			a[x - 1] = y;
		} else {
			int l, r;
			scanf("%d%d", &l, &r);
			--l;
			int len = r - l;
			for (int i = 0; i < len; ++i) {
				b[i] = std::make_pair(a[l + i], i);
				sum[i + 1] = sum[i] + a[l + i];
				le[i] = ri[i] = i;
				cnt[i] = 0;
				u[i] = 0;
			}
			//std::sort(b, b + len);
			countsort(len);
			for (int i = 0; i < len; ++i) {
				int id = b[i].second;
				u[id] = 1;
				int ll = id && u[id - 1] ? le[id - 1] : id, rr = id + 1 < len && u[id + 1] ? ri[id + 1] : id, curcnt = 1;
				if (sum[rr + 1] - sum[id + 1] >= sum[id + 1] - sum[id]) curcnt += cnt[id + 1];
				if (sum[id] - sum[ll] >= sum[id + 1] - sum[id]) curcnt += cnt[id - 1];
				ri[ll] = rr;
				le[rr] = ll;
				cnt[ll] = cnt[rr] = curcnt;
			}
			printf("%d\n", cnt[0]);
		}
	}
	return 0;
}

Compilation message

fish2.cpp: In function 'int main()':
fish2.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:25:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  for (int i = 0; i < n; ++i) scanf("%d", a + i);
      |                              ~~~~~^~~~~~~~~~~~~
fish2.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~
fish2.cpp:32:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |    scanf("%d%d", &x, &y);
      |    ~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:36:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 4 ms 2132 KB Output is correct
5 Incorrect 87 ms 2132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Incorrect 18 ms 4436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 4 ms 2132 KB Output is correct
5 Incorrect 87 ms 2132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Incorrect 18 ms 4436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2132 KB Output is correct
2 Incorrect 18 ms 4436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2132 KB Output is correct
2 Correct 2 ms 2132 KB Output is correct
3 Correct 8 ms 2132 KB Output is correct
4 Correct 4 ms 2132 KB Output is correct
5 Incorrect 87 ms 2132 KB Output isn't correct
6 Halted 0 ms 0 KB -