제출 #568888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568888		nonsensenonsense1	Fish 2 (JOI22_fish2)	C++17	0 / 100	87 ms	4436 KiB

fish2

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17