oj.uz

Submission #617433

# Submission time Handle Problem Language Result Execution time Memory
617433 2022-08-01T11:19:22 Z cheissmart Fish 2 (JOI22_fish2) C++14
60 / 100
 4000 ms 237580 KB 
// 花啊啊啊啊啊啊啊啊啊啊啊啊
#include <iostream>
#include <cstring>
#pragma GCC optimize("Ofast")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

const int INF = 1e9 + 7, N = 1e5 + 2;
const ll oo = 1e16;

ll a[N];
int n;

namespace cover {
	int t[N * 2];
	char tag[N * 2];
	int sum(int v, int h) { return tag[v] ? (1 << h) : t[v]; }
	void pull(int p) {
		int h = 0;
	    while(p > 1) {
	        t[p >> 1] = sum(p, h) + sum(p ^ 1, h);
	        p >>= 1;
	        h++;
	    }
	}
	void add(int l, int r, int x) {
		if(l == 1 && r == n + 1) return;
		l--, r--;
		int tl = l, tr = r;
	    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
	    	if(l & 1) tag[l++] += x;
	    	if(r & 1) tag[--r] += x;
	    }
	    pull(tl + n), pull(tr - 1 + n);
	}
	int qry(int l, int r) {
		l--, r--; 
	    int res = 0, h = 0;
	    for(l += n, r += n; l < r; l >>= 1, r >>= 1, h++) {
	        if(l & 1) res += sum(l++, h);
	        if(r & 1) res += sum(--r, h);
	    }
	    return res;
	}
}

namespace seg {
	template<class A, class B> struct DS {
		pair<A, B> a[29];
		int sz;
		DS() { sz = 0; }
		void clear() { sz = 0; }
		void EB(A& x, B& y) { a[sz++] = {x, y}; }
		void PB(pair<A, B>& p) { a[sz++] = p; }
		pair<A, B>& operator[](int i) { return a[i]; }
		void resize(int s) { sz = s; }
	};
	void cpy(DS<int, ll>& a, DS<int, ll>& b) {
		a.sz = b.sz;
		memcpy(a.a, b.a, a.sz * sizeof (a.a[0]));
	}
	struct node {
		DS<int, ll> bad_pref, bad_suff;
		DS<int, int> bad_seg;
		ll sum;
	} t[N * 2];

	int id(int tl, int tr) {
		tl--, tr -= 2;
	    return (tl + tr) | (tl != tr);
	}

	void pull(int v, int tl, int tr, int lc, int rc, int posl = INF, int posr = 0) {
		cpy(t[v].bad_pref, t[lc].bad_pref);
		cpy(t[v].bad_suff, t[rc].bad_suff);
		for(int i = 0; i < t[rc].bad_pref.sz; i++) {
			ll sum1 = t[rc].bad_pref[i].S + t[lc].sum;
			int pos1 = t[rc].bad_pref[i].F;
			if(sum1 + a[tl - 1] < a[pos1 + 1])
				t[v].bad_pref.EB(pos1, sum1);
		}
		for(int i = 0; i < t[lc].bad_suff.sz; i++) {
			ll sum1 = t[lc].bad_suff[i].S + t[rc].sum;
			int pos1 = t[lc].bad_suff[i].F;
			if(sum1 + a[tr] < a[pos1 - 1])
				t[v].bad_suff.EB(pos1, sum1);
		}

		int szi = t[lc].bad_suff.sz;
		int szj = t[rc].bad_pref.sz;
		int i = 0, j = 0;
		while(i < szi && t[lc].bad_suff[i].F > posl)
			i++;
		while(j < szj && t[rc].bad_pref[j].F < posr)
			j++;
		while(i < szi && j < szj) {
			auto& he = t[lc].bad_suff[i], be = t[rc].bad_pref[j];
			if(a[he.F - 1] < a[be.F + 1]) {
				if(he.S + be.S < a[he.F - 1]) {
					t[v].bad_seg.EB(he.F, be.F);
					cover::add(he.F, be.F + 1, 1);
				}
				i++;
			} else {
				if(he.S + be.S < a[be.F + 1]) {
					t[v].bad_seg.EB(he.F, be.F);
					cover::add(he.F, be.F + 1, 1);
				}
				j++;
			}
		}
		t[v].sum = t[lc].sum + t[rc].sum;
	}
	void build(int tl = 1, int tr = n + 1) {
		int v = id(tl, tr);
		if(tr - tl == 1) {
			t[v].sum = a[tl];
			if(a[tl] + a[tl - 1] < a[tl + 1])
				t[v].bad_pref.EB(tl, a[tl]);
			if(a[tl] + a[tl + 1] < a[tl - 1])
				t[v].bad_suff.EB(tl, a[tl]);
			if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) {
				t[v].bad_seg.EB(tl, tl);
				cover::add(tl, tl + 1, 1);
			}
		} else {
			int tm = (tl + tr + 1) / 2;
			build(tl, tm);
			build(tm, tr);
			pull(v, tl, tr, id(tl, tm), id(tm, tr));
		}
	}
	void upd(int pos, int tl = 1, int tr = n + 1) {
		int v = id(tl, tr);
		int j = 0;
		for(int i = 0; i < t[v].bad_seg.sz; i++) {
			auto [l, r] = t[v].bad_seg[i];
			if(r < pos - 1 || l > pos + 1) {
				t[v].bad_seg[j++] = t[v].bad_seg[i];
			} else {
				cover::add(l, r + 1, -1);
			}
		}
		t[v].bad_seg.resize(j);

		t[v].bad_pref.clear(), t[v].bad_suff.clear();
		if(tr - tl == 1) {
			t[v].sum = a[tl];
			if(a[tl] + a[tl - 1] < a[tl + 1])
				t[v].bad_pref.EB(tl, a[tl]);
			if(a[tl] + a[tl + 1] < a[tl - 1])
				t[v].bad_suff.EB(tl, a[tl]);
			if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) {
				t[v].bad_seg.EB(tl, tl);
				cover::add(tl, tl + 1, 1);
			}
		} else {
			int tm = (tl + tr + 1) / 2;
			if(pos - 1 < tm)
				upd(pos, tl, tm);
			if(pos + 1 >= tm)
				upd(pos, tm, tr);
			pull(v, tl, tr, id(tl, tm), id(tm, tr), pos + 1, pos - 1);
		}
	}
}

void upd(int pos, ll val) {
	a[pos] = val;
	seg::upd(pos);
}

#define gc getchar_unlocked
inline int readInt () {
	int c = gc();
	while(!isdigit(c)) c = gc();
	int res = c - '0';
	while(isdigit(c = gc())) res = res * 10 + c - '0';
	return res;
}


#define pc(x) putchar_unlocked(x);
inline void writeInt (int n) {
    int N = n, rev, count = 0;
    rev = N;
    if (N == 0) { pc('0'); return ;}
    while ((rev % 10) == 0) { count++; rev /= 10;}
    rev = 0;
    while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
    while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
    while (count--) pc('0');
}

signed main()
{
	IO_OP;

	n = readInt();
	a[0] = a[n + 1] = oo;
	for(int i = 1; i <= n; i++)
		a[i] = readInt();

	seg::build();

	int q = readInt();
	while(q--) {
		int op = readInt();
		if(op == 1) {
			int x = readInt(), y = readInt();
			upd(x, y);
		} else {
			int l = readInt(), r = readInt();
			ll tl = a[l - 1], tr = a[r + 1];

			if(l - 1 >= 1) upd(l - 1, 1e15);
			if(r + 1 <= n) upd(r + 1, 1e15);
			if(l != 1 || r != n)
				cover::add(l, r + 1, -1);

			writeInt(r - l + 1 - cover::qry(l, r + 1));
			pc('\n');

			if(l != 1 || r != n)
				cover::add(l, r + 1, 1);

			if(l - 1 >= 1) upd(l - 1, tl);
			if(r + 1 <= n) upd(r + 1, tr);
		}
	}

}

Compilation message

fish2.cpp: In function 'void seg::cpy(seg::DS<int, long long int>&, seg::DS<int, long long int>&)':
fish2.cpp:71:42: warning: 'void* memcpy(void*, const void*, size_t)' writing to an object of type 'struct std::pair<int, long long int>' with no trivial copy-assignment; use copy-assignment or copy-initialization instead [-Wclass-memaccess]
   71 |   memcpy(a.a, b.a, a.sz * sizeof (a.a[0]));
      |                                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from fish2.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
fish2.cpp: In function 'void seg::upd(int, int, int)':
fish2.cpp:148:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |    auto [l, r] = t[v].bad_seg[i];
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 233532 KB Output is correct
2 Correct 129 ms 233536 KB Output is correct
3 Correct 129 ms 233588 KB Output is correct
4 Correct 122 ms 233560 KB Output is correct
5 Correct 131 ms 233548 KB Output is correct
6 Correct 173 ms 233484 KB Output is correct
7 Correct 106 ms 233496 KB Output is correct
8 Correct 120 ms 233604 KB Output is correct
9 Correct 127 ms 233500 KB Output is correct
10 Correct 113 ms 233564 KB Output is correct
11 Correct 111 ms 233596 KB Output is correct
12 Correct 114 ms 233524 KB Output is correct
13 Correct 168 ms 233560 KB Output is correct
14 Correct 107 ms 233556 KB Output is correct
15 Correct 121 ms 233536 KB Output is correct
16 Correct 111 ms 233600 KB Output is correct
17 Correct 117 ms 233536 KB Output is correct
18 Correct 111 ms 233524 KB Output is correct
19 Correct 101 ms 233592 KB Output is correct
20 Correct 107 ms 233696 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 233584 KB Output is correct
2 Correct 136 ms 235404 KB Output is correct
3 Correct 123 ms 235260 KB Output is correct
4 Correct 129 ms 235484 KB Output is correct
5 Correct 126 ms 235216 KB Output is correct
6 Correct 120 ms 235792 KB Output is correct
7 Correct 114 ms 235124 KB Output is correct
8 Correct 146 ms 235912 KB Output is correct
9 Correct 131 ms 235096 KB Output is correct
10 Correct 126 ms 235476 KB Output is correct
11 Correct 143 ms 235232 KB Output is correct
12 Correct 115 ms 235140 KB Output is correct
13 Correct 115 ms 235148 KB Output is correct
14 Correct 122 ms 235504 KB Output is correct
15 Correct 120 ms 235532 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 233532 KB Output is correct
2 Correct 129 ms 233536 KB Output is correct
3 Correct 129 ms 233588 KB Output is correct
4 Correct 122 ms 233560 KB Output is correct
5 Correct 131 ms 233548 KB Output is correct
6 Correct 173 ms 233484 KB Output is correct
7 Correct 106 ms 233496 KB Output is correct
8 Correct 120 ms 233604 KB Output is correct
9 Correct 127 ms 233500 KB Output is correct
10 Correct 113 ms 233564 KB Output is correct
11 Correct 111 ms 233596 KB Output is correct
12 Correct 114 ms 233524 KB Output is correct
13 Correct 168 ms 233560 KB Output is correct
14 Correct 107 ms 233556 KB Output is correct
15 Correct 121 ms 233536 KB Output is correct
16 Correct 111 ms 233600 KB Output is correct
17 Correct 117 ms 233536 KB Output is correct
18 Correct 111 ms 233524 KB Output is correct
19 Correct 101 ms 233592 KB Output is correct
20 Correct 107 ms 233696 KB Output is correct
21 Correct 113 ms 233584 KB Output is correct
22 Correct 136 ms 235404 KB Output is correct
23 Correct 123 ms 235260 KB Output is correct
24 Correct 129 ms 235484 KB Output is correct
25 Correct 126 ms 235216 KB Output is correct
26 Correct 120 ms 235792 KB Output is correct
27 Correct 114 ms 235124 KB Output is correct
28 Correct 146 ms 235912 KB Output is correct
29 Correct 131 ms 235096 KB Output is correct
30 Correct 126 ms 235476 KB Output is correct
31 Correct 143 ms 235232 KB Output is correct
32 Correct 115 ms 235140 KB Output is correct
33 Correct 115 ms 235148 KB Output is correct
34 Correct 122 ms 235504 KB Output is correct
35 Correct 120 ms 235532 KB Output is correct
36 Correct 158 ms 235468 KB Output is correct
37 Correct 172 ms 235300 KB Output is correct
38 Correct 161 ms 235292 KB Output is correct
39 Correct 137 ms 235444 KB Output is correct
40 Correct 180 ms 235180 KB Output is correct
41 Correct 130 ms 235932 KB Output is correct
42 Correct 130 ms 235960 KB Output is correct
43 Correct 146 ms 235144 KB Output is correct
44 Correct 140 ms 235176 KB Output is correct
45 Correct 162 ms 235420 KB Output is correct
46 Correct 138 ms 235432 KB Output is correct
47 Correct 139 ms 235248 KB Output is correct
48 Correct 123 ms 235212 KB Output is correct
49 Correct 131 ms 235264 KB Output is correct
50 Correct 139 ms 235564 KB Output is correct
51 Correct 131 ms 235520 KB Output is correct
52 Correct 137 ms 235540 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 233584 KB Output is correct
2 Correct 136 ms 235404 KB Output is correct
3 Correct 123 ms 235260 KB Output is correct
4 Correct 129 ms 235484 KB Output is correct
5 Correct 126 ms 235216 KB Output is correct
6 Correct 120 ms 235792 KB Output is correct
7 Correct 114 ms 235124 KB Output is correct
8 Correct 146 ms 235912 KB Output is correct
9 Correct 131 ms 235096 KB Output is correct
10 Correct 126 ms 235476 KB Output is correct
11 Correct 143 ms 235232 KB Output is correct
12 Correct 115 ms 235140 KB Output is correct
13 Correct 115 ms 235148 KB Output is correct
14 Correct 122 ms 235504 KB Output is correct
15 Correct 120 ms 235532 KB Output is correct
16 Correct 103 ms 233688 KB Output is correct
17 Correct 3722 ms 236980 KB Output is correct
18 Correct 3382 ms 237212 KB Output is correct
19 Correct 3726 ms 236984 KB Output is correct
20 Execution timed out 4108 ms 235636 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 233584 KB Output is correct
2 Correct 136 ms 235404 KB Output is correct
3 Correct 123 ms 235260 KB Output is correct
4 Correct 129 ms 235484 KB Output is correct
5 Correct 126 ms 235216 KB Output is correct
6 Correct 120 ms 235792 KB Output is correct
7 Correct 114 ms 235124 KB Output is correct
8 Correct 146 ms 235912 KB Output is correct
9 Correct 131 ms 235096 KB Output is correct
10 Correct 126 ms 235476 KB Output is correct
11 Correct 143 ms 235232 KB Output is correct
12 Correct 115 ms 235140 KB Output is correct
13 Correct 115 ms 235148 KB Output is correct
14 Correct 122 ms 235504 KB Output is correct
15 Correct 120 ms 235532 KB Output is correct
16 Correct 110 ms 233544 KB Output is correct
17 Correct 703 ms 236476 KB Output is correct
18 Correct 602 ms 236900 KB Output is correct
19 Correct 578 ms 236492 KB Output is correct
20 Correct 534 ms 236880 KB Output is correct
21 Correct 654 ms 236584 KB Output is correct
22 Correct 601 ms 236980 KB Output is correct
23 Correct 550 ms 236368 KB Output is correct
24 Correct 558 ms 236924 KB Output is correct
25 Correct 528 ms 236576 KB Output is correct
26 Correct 320 ms 237580 KB Output is correct
27 Correct 330 ms 237560 KB Output is correct
28 Correct 467 ms 236816 KB Output is correct
29 Correct 295 ms 237504 KB Output is correct
30 Correct 356 ms 237556 KB Output is correct
31 Correct 486 ms 237008 KB Output is correct
32 Correct 537 ms 236896 KB Output is correct
33 Correct 341 ms 236536 KB Output is correct
34 Correct 524 ms 237212 KB Output is correct
35 Correct 333 ms 236900 KB Output is correct
36 Correct 536 ms 236928 KB Output is correct
37 Correct 465 ms 236620 KB Output is correct
38 Correct 325 ms 236796 KB Output is correct
39 Correct 385 ms 237156 KB Output is correct
40 Correct 222 ms 237212 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 233532 KB Output is correct
2 Correct 129 ms 233536 KB Output is correct
3 Correct 129 ms 233588 KB Output is correct
4 Correct 122 ms 233560 KB Output is correct
5 Correct 131 ms 233548 KB Output is correct
6 Correct 173 ms 233484 KB Output is correct
7 Correct 106 ms 233496 KB Output is correct
8 Correct 120 ms 233604 KB Output is correct
9 Correct 127 ms 233500 KB Output is correct
10 Correct 113 ms 233564 KB Output is correct
11 Correct 111 ms 233596 KB Output is correct
12 Correct 114 ms 233524 KB Output is correct
13 Correct 168 ms 233560 KB Output is correct
14 Correct 107 ms 233556 KB Output is correct
15 Correct 121 ms 233536 KB Output is correct
16 Correct 111 ms 233600 KB Output is correct
17 Correct 117 ms 233536 KB Output is correct
18 Correct 111 ms 233524 KB Output is correct
19 Correct 101 ms 233592 KB Output is correct
20 Correct 107 ms 233696 KB Output is correct
21 Correct 113 ms 233584 KB Output is correct
22 Correct 136 ms 235404 KB Output is correct
23 Correct 123 ms 235260 KB Output is correct
24 Correct 129 ms 235484 KB Output is correct
25 Correct 126 ms 235216 KB Output is correct
26 Correct 120 ms 235792 KB Output is correct
27 Correct 114 ms 235124 KB Output is correct
28 Correct 146 ms 235912 KB Output is correct
29 Correct 131 ms 235096 KB Output is correct
30 Correct 126 ms 235476 KB Output is correct
31 Correct 143 ms 235232 KB Output is correct
32 Correct 115 ms 235140 KB Output is correct
33 Correct 115 ms 235148 KB Output is correct
34 Correct 122 ms 235504 KB Output is correct
35 Correct 120 ms 235532 KB Output is correct
36 Correct 158 ms 235468 KB Output is correct
37 Correct 172 ms 235300 KB Output is correct
38 Correct 161 ms 235292 KB Output is correct
39 Correct 137 ms 235444 KB Output is correct
40 Correct 180 ms 235180 KB Output is correct
41 Correct 130 ms 235932 KB Output is correct
42 Correct 130 ms 235960 KB Output is correct
43 Correct 146 ms 235144 KB Output is correct
44 Correct 140 ms 235176 KB Output is correct
45 Correct 162 ms 235420 KB Output is correct
46 Correct 138 ms 235432 KB Output is correct
47 Correct 139 ms 235248 KB Output is correct
48 Correct 123 ms 235212 KB Output is correct
49 Correct 131 ms 235264 KB Output is correct
50 Correct 139 ms 235564 KB Output is correct
51 Correct 131 ms 235520 KB Output is correct
52 Correct 137 ms 235540 KB Output is correct
53 Correct 103 ms 233688 KB Output is correct
54 Correct 3722 ms 236980 KB Output is correct
55 Correct 3382 ms 237212 KB Output is correct
56 Correct 3726 ms 236984 KB Output is correct
57 Execution timed out 4108 ms 235636 KB Time limit exceeded
58 Halted 0 ms 0 KB -