Submission #614197

# Submission time Handle Problem Language Result Execution time Memory
614197 2022-07-30T21:41:07 Z GusterGoose27 Ruka (COI15_ruka) C++11
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const ll MAXN = 1e5;
ll n, q;
const ll BSIZE = 301;
const ll MAXBLOCKS = 333;
ll num_blocks;
ll numsx[MAXN];
ll numsy[MAXN];
pii vecs[MAXN];

ll sign(ll v) {
	if (v == 0) return 0;
	if (v < 0) return -1;
	return 1;
}

class Block {
public:
	vector<ll> xstart;
	vector<ll> xend;
	vector<ll> ystart;
	vector<ll> yend;
	ll shiftx = 0;
	ll shifty = 0;
	ll lp, rp;
	Block() {}
	Block(ll lv, ll rv) {
		lp = lv;
		rp = rv;
		make();
	}
	void make() {
		xstart.clear();
		xend.clear();
		ystart.clear();
		yend.clear();
		for (ll i = lp; i <= rp; i++) {
			if (i > lp) {
				ll x1 = numsx[i];
				ll x2 = numsx[i-1];
				ll y1 = numsy[i];
				ll y2 = numsy[i-1];
				ll mnx = min(x1, x2);
				ll mxx = max(x1, x2);
				ll mny = min(y1, y2);
				ll mxy = max(y1, y2);
				xstart.push_back(-mxx);
				xend.push_back(-mnx);
				ystart.push_back(-mxy);
				yend.push_back(-mny);
			}
		}
		sort(xstart.begin(), xstart.end());
		sort(ystart.begin(), ystart.end());
		sort(xend.begin(), xend.end());
		sort(yend.begin(), yend.end());
	}
	ll bs(vector<ll> &v, ll pos) {
		ll mn = -1;
		ll mx = v.size();
		while (mx > mn+1) {
			ll cur = (mn+mx)/2;
			if (v[cur] < pos) mn = cur;
			else mx = cur;
			assert(v[cur] != pos);
		}
		return mn+1;
	}
	ll get() {
		return bs(xstart, shiftx)+bs(ystart, shifty)-bs(xend, shiftx)-bs(yend, shifty);
	}
	void upd(ll l, ll r, ll vx, ll vy) {
		for (ll i = lp; i <= rp; i++) {
			numsx[i] += shiftx;
			numsy[i] += shifty;
			if (l <= i && i <= r) {
				numsx[i] += vx;
				numsy[i] += vy;
			}
		}
		shiftx = 0;
		shifty = 0;
		make();
	}
};

Block blocks[MAXBLOCKS];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	num_blocks = ceil((1.0*(n+1))/BSIZE);
	ll curx = 1;
	ll cury = 1;
	for (ll i = 0; i < n; i++) {
		numsx[i] = curx;
		numsy[i] = cury;
		ll x, y; cin >> x >> y;
		curx += x;
		cury += y;
		vecs[i] = pii(x, y);
	}
	numsx[n] = curx;
	numsy[n] = cury;
	for (ll i = 0; i < num_blocks; i++) {
		blocks[i] = Block(BSIZE*i, min(BSIZE*(i+1), n));
	}
	ll pos = 0;
	cin >> q;
	for (ll i = 0; i < q; i++) {
		char c; cin >> c;
		if (c == 'Q') {
			ll ans = 0;
			for (ll j = 0; j < num_blocks; j++) {
				ans += blocks[j].get();
				if (j < num_blocks-1) {
					ll x1 = numsx[blocks[j].rp]+blocks[j].shiftx;
					ll y1 = numsy[blocks[j].rp]+blocks[j].shifty;
					ll x2 = numsx[blocks[j+1].lp]+blocks[j+1].shiftx;
					ll y2 = numsy[blocks[j+1].lp]+blocks[j+1].shifty;
					ans += (sign(x1) != sign(x2)) + (sign(y1) != sign(y2));
				}
			}
			cout << ans << "\n";
		}
		if (c == 'B') {
			pos = max(pos-1, 0);
		}
		if (c == 'F') {
			pos = min(n-1, pos+1);
		}
		if (c == 'C') {
			ll x, y; cin >> x >> y;
			ll xsh = x-vecs[pos].first;
			ll ysh = y-vecs[pos].second;
			vecs[pos] = pii(x, y);
			for (ll j = 0; j < num_blocks; j++) {
				if (blocks[j].rp <= pos) continue;
				if (blocks[j].lp <= pos) {
					blocks[j].upd(pos+1, blocks[j].rp, xsh, ysh);
				}
				else {
					blocks[j].shiftx += xsh;
					blocks[j].shifty += ysh;
				}
			}
		}
	}
}

Compilation message

ruka.cpp: In function 'int main()':
ruka.cpp:133:22: error: no matching function for call to 'max(ll, int)'
  133 |    pos = max(pos-1, 0);
      |                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ruka.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
ruka.cpp:133:22: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  133 |    pos = max(pos-1, 0);
      |                      ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from ruka.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
ruka.cpp:133:22: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  133 |    pos = max(pos-1, 0);
      |                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from ruka.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
ruka.cpp:133:22: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  133 |    pos = max(pos-1, 0);
      |                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from ruka.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
ruka.cpp:133:22: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  133 |    pos = max(pos-1, 0);
      |                      ^