oj.uz

Submission #569015

# Submission time Handle Problem Language Result Execution time Memory
569015 2022-05-26T13:28:49 Z nonsensenonsense1 Fish 2 (JOI22_fish2) C++17
0 / 100
 73 ms 29796 KB 
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>

const int N = 100005;
int n, q, a[N];

struct info {
	int cnt, need;
	long long sum;
};

struct item {
	std::vector<info> pref, suf;
	item() {}
	item(int x) {
		pref.push_back({1, x, x});
		suf.push_back(pref.back());
	}
} t[N * 2];

item operator+(item a, item b) {
	if (a.pref.empty()) return b;
	if (b.pref.empty()) return a;
	item res;
	res.pref = a.pref;
	res.pref.back().cnt = 0;
	int i;
	for (i = 0; i < b.pref.size() && b.pref[i].need <= res.pref.back().sum; ++i) 
		res.pref.back().sum = b.pref[i].sum + a.pref.back().sum;
	for (; i < b.pref.size(); ++i) {
		res.pref.push_back(b.pref[i]);
		if (i + 1 == b.pref.size()) res.pref.back().cnt = 0;
		res.pref.back().sum += a.pref.back().sum;
	}
	res.suf = b.suf;
	res.suf.back().cnt = 0;
	for (i = 0; i < a.suf.size() && a.suf[i].need <= res.suf.back().sum; ++i) 
		res.suf.back().sum = a.suf[i].sum + b.pref.back().sum;
	for (; i < a.suf.size(); ++i) {
		res.suf.push_back(a.suf[i]);
		if (i + 1 == a.suf.size()) res.suf.back().cnt = 0;
		res.suf.back().sum += b.pref.back().sum;
	}
	for (int t = 0; t < 2; ++t) {
		for (int i = 0;; ++i) {
			int j, k, amt;
			long long s;
			if (t) {
				if (i == a.suf.size()) break;
				s = a.suf[i].sum;
				j = i + 1;
				k = 0;
				amt = a.suf[i].cnt;
			} else {
				if (i == b.pref.size()) break;
				s = b.pref[i].sum;
				j = 0;
				k = i + 1;
				amt = b.pref[i].cnt;
			}
			while (true) {
				if (j < a.suf.size() && s >= a.suf[j].need) {
					s += a.suf[j].sum - (j ? a.suf[j - 1].sum : 0);
					++j;
				} else if (k < b.pref.size() && s >= b.pref[k].need) {
					s += b.pref[k].sum - (k ? b.pref[k - 1].sum : 0);
					++k;
				} else break;
			}
			if (j == a.suf.size()) {
				if (k == b.pref.size()) {
					res.pref.back().cnt += amt;
					res.suf.back().cnt += amt;
				} else {
					int l;
					for (l = 0; res.pref[l].need != b.pref[k].need; ++l);
					res.pref[l - 1].cnt += amt;
				}
			} else if (k == b.pref.size()) {
				int l;
				for (l = 0; res.suf[l].need != a.suf[j].need; ++l);
				res.suf[l - 1].cnt += amt;
			}
		}
	}
	return res;
}

void build(int v = 0, int tl = 0, int tr = n) {
	if (tr - tl == 1) t[v] = item(a[tl]);
	else {
		int m = tl + tr >> 1;
		build(v + 1, tl, m);
		build(v + (tr - tl & ~1), m, tr);
		t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
	}
}

void update(int i, int x, int v = 0, int tl = 0, int tr = n) {
	if (tr - tl == 1) t[v] = item(x);
	else {
		int m = tl + tr >> 1;
		if (i < m) update(i, x, v + 1, tl, m);
		else update(i, x, v + (tr - tl & ~1), m, tr);
		t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
	}
}

item query(int l, int r, int v = 0, int tl = 0, int tr = n) {
	if (tl >= r || tr <= l) return item();
	if (tl >= l && tr <= r) return t[v];
	int m = tl + tr >> 1;
	return query(l, r, v + 1, tl, m) + query(l, r, v + (tr - tl & ~1), m, tr);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	build();
	scanf("%d", &q);
	while (q--) {
		int type;
		scanf("%d", &type);
		if (type == 1) {
			int i, x;
			scanf("%d%d", &i, &x);
			update(i - 1, x);
		} else {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%d\n", query(l - 1, r).pref.back().cnt);
		}
	}
	return 0;
}

Compilation message

fish2.cpp: In function 'item operator+(item, item)':
fish2.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (i = 0; i < b.pref.size() && b.pref[i].need <= res.pref.back().sum; ++i)
      |              ~~^~~~~~~~~~~~~~~
fish2.cpp:33:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for (; i < b.pref.size(); ++i) {
      |         ~~^~~~~~~~~~~~~~~
fish2.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   if (i + 1 == b.pref.size()) res.pref.back().cnt = 0;
      |       ~~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (i = 0; i < a.suf.size() && a.suf[i].need <= res.suf.back().sum; ++i)
      |              ~~^~~~~~~~~~~~~~
fish2.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (; i < a.suf.size(); ++i) {
      |         ~~^~~~~~~~~~~~~~
fish2.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if (i + 1 == a.suf.size()) res.suf.back().cnt = 0;
      |       ~~~~~~^~~~~~~~~~~~~~~
fish2.cpp:52:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if (i == a.suf.size()) break;
      |         ~~^~~~~~~~~~~~~~~
fish2.cpp:58:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if (i == b.pref.size()) break;
      |         ~~^~~~~~~~~~~~~~~~
fish2.cpp:65:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     if (j < a.suf.size() && s >= a.suf[j].need) {
      |         ~~^~~~~~~~~~~~~~
fish2.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     } else if (k < b.pref.size() && s >= b.pref[k].need) {
      |                ~~^~~~~~~~~~~~~~~
fish2.cpp:73:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    if (j == a.suf.size()) {
      |        ~~^~~~~~~~~~~~~~~
fish2.cpp:74:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     if (k == b.pref.size()) {
      |         ~~^~~~~~~~~~~~~~~~
fish2.cpp:82:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    } else if (k == b.pref.size()) {
      |               ~~^~~~~~~~~~~~~~~~
fish2.cpp: In function 'void build(int, int, int)':
fish2.cpp:95:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |   int m = tl + tr >> 1;
      |           ~~~^~~~
fish2.cpp:97:17: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   97 |   build(v + (tr - tl & ~1), m, tr);
      |              ~~~^~~~
fish2.cpp:98:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   98 |   t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
      |                            ~~~^~~~
fish2.cpp: In function 'void update(int, int, int, int, int)':
fish2.cpp:105:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |   int m = tl + tr >> 1;
      |           ~~~^~~~
fish2.cpp:107:29: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  107 |   else update(i, x, v + (tr - tl & ~1), m, tr);
      |                          ~~~^~~~
fish2.cpp:108:31: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  108 |   t[v] = t[v + 1] + t[v + (tr - tl & ~1)];
      |                            ~~~^~~~
fish2.cpp: In function 'item query(int, int, int, int, int)':
fish2.cpp:115:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |  int m = tl + tr >> 1;
      |          ~~~^~~~
fish2.cpp:116:57: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  116 |  return query(l, r, v + 1, tl, m) + query(l, r, v + (tr - tl & ~1), m, tr);
      |                                                      ~~~^~~~
fish2.cpp: In function 'int main()':
fish2.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:121:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  for (int i = 0; i < n; ++i) scanf("%d", a + i);
      |                              ~~~~~^~~~~~~~~~~~~
fish2.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
fish2.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |   scanf("%d", &type);
      |   ~~~~~^~~~~~~~~~~~~
fish2.cpp:129:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |    scanf("%d%d", &i, &x);
      |    ~~~~~^~~~~~~~~~~~~~~~
fish2.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |    scanf("%d%d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9692 KB Output is correct
2 Incorrect 73 ms 29796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9692 KB Output is correct
2 Incorrect 73 ms 29796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9692 KB Output is correct
2 Incorrect 73 ms 29796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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