Submission #410647

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410647	2021-05-23T08:41:44 Z	hhhhaura	Land of the Rainbow Gold (APIO17_rainbow)	C++14	Compilation error	0 ms	0 KB

rainbow

//#define wiwihorz
#include "rainbow.h"
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define INF 1000000000
using namespace std;
#define ll long long int
#define pii pair<ll, ll>
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
#define x first
#define y second
//namespace solver1 {
	ll n, m, sr, sc, op; string s;
	vector<vector<ll>> row1, col1;
	vector<vector<pii>> row2, col2;
	unordered_map<char, pii> mp = {
		{'N', {-1, 0}}, {'S', {1, 0}},
		{'E', {0, 1}}, {'W', {0, -1}}
	};
	void init_(int _n, int _m, int _sr, int _sc, int _op, char* _s) {
		n = _n, m = _m, sr = _sr, sc = _sc, op = _op, s = string(_s);
		row1.assign(n + 1, vector<ll>());
		row2.assign(n + 1, vector<pii>());
		col1.assign(m + 1, vector<ll>());
		col2.assign(m + 1, vector<pii>());
		pii cur = {sr, sc};
		row1[cur.x].push_back(cur.y);
		col1[cur.y].push_back(cur.x);
		for(auto i : s) {
			cur = {cur.x + mp[i].x, cur.y + mp[i].y};
			row1[cur.x].push_back(cur.y);
			col1[cur.y].push_back(cur.x);
		}
		rep(i, 1, n) {
			sort(all(row1[i]));
			row1[i].resize(unique(all(row1[i])) - row1[i].begin());
			ll cc = -1, val = 0;
			for(auto j : row1[i]) {
				if(cc + 1 != j) {
					if(val) row2[i].push_back({cc, val});
					row2[i].push_back({j, j}), val = j;
				}
				cc = j;
			}
			if(cc != -1)row2[i].push_back({cc, val});
		}
		rep(i, 1, m) {
			sort(all(col1[i]));
			col1[i].resize(unique(all(col1[i])) - col1[i].begin());
			ll cc = -1, val = 0;
			for(auto j : col1[i]) {
				if(cc + 1 != j) {
					if(val) col2[i].push_back({cc, val});
					col2[i].push_back({j, j}), val = j;
				}
				cc = j;
			}
			if(cc != -1)col2[i].push_back({cc, val});
		}
		return;
	}
	ll area(int u, int d, int l, int r) {
		ll ans = 0;
		rep(i, u, d) {
			
			int L = upper_bound(row1[i].begin(), row1[i].end(), l - 1) - row1[i].begin();
			int R = upper_bound(row1[i].begin(), row1[i].end(), r) - row1[i].begin();
			print(i, L, R);
			vprint(all(row1[i]));
			ans += R - L;
		}
		return ans;
	}
	bool occ(int x, int y) {
		int id = lower_bound(row1[x].begin(), row1[x].end(), y) - row1[x].begin();
		return id < row1[x].size() && row1[x][id] == y;
	}
	ll count_row(int id, int L, int R) {
		ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
		ll rid = upper_bound(row2[id].begin(), row2[id].end(), pii(R, INF)) - row2[id].begin() - 1;
		if(lid > rid) return 0;
		if(lid && row2[id][lid - 1].y == row2[id][lid].y) lid --;
		if(rid + 1 < row2[id].size() && row2[id][rid + 1].y == row2[id][rid].y) rid ++;
		assert((rid - lid + 1) % 2 == 0);
		return (rid - lid + 1) / 2;
	}
	ll count_col(int id, int L, int R) {
		ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
		ll rid = upper_bound(col2[id].begin(), col2[id].end(), pii(R, INF)) - col2[id].begin() - 1;
		if(lid > rid) return 0;
		if(lid && col2[id][lid - 1].y == col2[id][lid].y) lid --;
		if(rid + 1 < col2[id].size() && col2[id][rid + 1].y == col2[id][rid].y) rid ++;
		assert((rid - lid + 1) % 2 == 0);
		return (rid - lid + 1) / 2;
	}
	int colours(int ar, int ac, int br, int bc) {
		int u = min(ar, br), d = max(ar, br);
		int l = min(ac, bc), r = max(ac, bc);
		ll count = area(u, d, l, r);

		if(!count) return 1;
		if(count == ((d - u + 1) * (r - l + 1))) return 0;
		ll ans = count_row(u, l, r - 1) + count_row(d, l + 1, r) + 
			count_col(l, u + 1, d) + count_col(r, u, d - 1);

		if(occ(u, r - 1) && occ(u, r)) ans --;
		if(occ(d - 1, r) && occ(d, r)) ans --;
		if(occ(d, l) && occ(d, l + 1)) ans --;
		if(occ(u, l) && occ(u + 1, l)) ans --;
		return ans;
	}
//};
//using namespace solver1;
/*signed main() {
//	ios::sync_with_stdio(false), cin.tie(0);
	int n, m, sr, sc, op, q; char* s;
	cin >> n >> m >> sr >> sc >> op >> s;
	init_(n, m, sr, sc, op, s);
	cin >> q;
	while(q--) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		cout << colours(a, b, c, d) << "\n";
	}
	
	return 0;
} */

Compilation message

rainbow.cpp:22:23: error: 'string' does not name a type
   22 |  ll n, m, sr, sc, op; string s;
      |                       ^~~~~~
rainbow.cpp:23:2: error: 'vector' does not name a type
   23 |  vector<vector<ll>> row1, col1;
      |  ^~~~~~
rainbow.cpp:24:2: error: 'vector' does not name a type
   24 |  vector<vector<pii>> row2, col2;
      |  ^~~~~~
rainbow.cpp:25:2: error: 'unordered_map' does not name a type
   25 |  unordered_map<char, pii> mp = {
      |  ^~~~~~~~~~~~~
rainbow.cpp: In function 'void init_(int, int, int, int, int, char*)':
rainbow.cpp:30:49: error: 's' was not declared in this scope; did you mean '_s'?
   30 |   n = _n, m = _m, sr = _sr, sc = _sc, op = _op, s = string(_s);
      |                                                 ^
      |                                                 _s
rainbow.cpp:30:53: error: 'string' was not declared in this scope
   30 |   n = _n, m = _m, sr = _sr, sc = _sc, op = _op, s = string(_s);
      |                                                     ^~~~~~
rainbow.cpp:3:1: note: 'std::string' is defined in header '<string>'; did you forget to '#include <string>'?
    2 | #include "rainbow.h"
  +++ |+#include <string>
    3 | #define rep(i, a, b) for(int i = a; i <= b; i++)
rainbow.cpp:31:3: error: 'row1' was not declared in this scope
   31 |   row1.assign(n + 1, vector<ll>());
      |   ^~~~
rainbow.cpp:31:22: error: 'vector' was not declared in this scope
   31 |   row1.assign(n + 1, vector<ll>());
      |                      ^~~~~~
rainbow.cpp:3:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    2 | #include "rainbow.h"
  +++ |+#include <vector>
    3 | #define rep(i, a, b) for(int i = a; i <= b; i++)
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:31:29: note: in expansion of macro 'll'
   31 |   row1.assign(n + 1, vector<ll>());
      |                             ^~
rainbow.cpp:32:3: error: 'row2' was not declared in this scope
   32 |   row2.assign(n + 1, vector<pii>());
      |   ^~~~
rainbow.cpp:9:13: error: 'pair' was not declared in this scope
    9 | #define pii pair<ll, ll>
      |             ^~~~
rainbow.cpp:32:29: note: in expansion of macro 'pii'
   32 |   row2.assign(n + 1, vector<pii>());
      |                             ^~~
rainbow.cpp:3:1: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
    2 | #include "rainbow.h"
  +++ |+#include <utility>
    3 | #define rep(i, a, b) for(int i = a; i <= b; i++)
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:32:29: note: in expansion of macro 'pii'
   32 |   row2.assign(n + 1, vector<pii>());
      |                             ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:22: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                      ^~
rainbow.cpp:32:29: note: in expansion of macro 'pii'
   32 |   row2.assign(n + 1, vector<pii>());
      |                             ^~~
rainbow.cpp:33:3: error: 'col1' was not declared in this scope
   33 |   col1.assign(m + 1, vector<ll>());
      |   ^~~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:33:29: note: in expansion of macro 'll'
   33 |   col1.assign(m + 1, vector<ll>());
      |                             ^~
rainbow.cpp:34:3: error: 'col2' was not declared in this scope
   34 |   col2.assign(m + 1, vector<pii>());
      |   ^~~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:34:29: note: in expansion of macro 'pii'
   34 |   col2.assign(m + 1, vector<pii>());
      |                             ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:22: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                      ^~
rainbow.cpp:34:29: note: in expansion of macro 'pii'
   34 |   col2.assign(m + 1, vector<pii>());
      |                             ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:35:3: note: in expansion of macro 'pii'
   35 |   pii cur = {sr, sc};
      |   ^~~
rainbow.cpp:36:8: error: 'cur' was not declared in this scope
   36 |   row1[cur.x].push_back(cur.y);
      |        ^~~
rainbow.cpp:39:19: error: 'mp' was not declared in this scope; did you mean 'op'?
   39 |    cur = {cur.x + mp[i].x, cur.y + mp[i].y};
      |                   ^~
      |                   op
rainbow.cpp:44:4: error: 'sort' was not declared in this scope; did you mean 'short'?
   44 |    sort(all(row1[i]));
      |    ^~~~
      |    short
rainbow.cpp:45:19: error: 'unique' was not declared in this scope
   45 |    row1[i].resize(unique(all(row1[i])) - row1[i].begin());
      |                   ^~~~~~
rainbow.cpp:57:4: error: 'sort' was not declared in this scope; did you mean 'short'?
   57 |    sort(all(col1[i]));
      |    ^~~~
      |    short
rainbow.cpp:58:19: error: 'unique' was not declared in this scope
   58 |    col1[i].resize(unique(all(col1[i])) - col1[i].begin());
      |                   ^~~~~~
rainbow.cpp: In function 'long long int area(int, int, int, int)':
rainbow.cpp:75:24: error: 'row1' was not declared in this scope
   75 |    int L = upper_bound(row1[i].begin(), row1[i].end(), l - 1) - row1[i].begin();
      |                        ^~~~
rainbow.cpp:75:12: error: 'upper_bound' was not declared in this scope
   75 |    int L = upper_bound(row1[i].begin(), row1[i].end(), l - 1) - row1[i].begin();
      |            ^~~~~~~~~~~
rainbow.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define print(...) 0
      |                    ^
rainbow.cpp:77:4: note: in expansion of macro 'print'
   77 |    print(i, L, R);
      |    ^~~~~
rainbow.cpp:17:21: warning: statement has no effect [-Wunused-value]
   17 | #define vprint(...) 0
      |                     ^
rainbow.cpp:78:4: note: in expansion of macro 'vprint'
   78 |    vprint(all(row1[i]));
      |    ^~~~~~
rainbow.cpp: In function 'bool occ(int, int)':
rainbow.cpp:84:24: error: 'row1' was not declared in this scope
   84 |   int id = lower_bound(row1[x].begin(), row1[x].end(), y) - row1[x].begin();
      |                        ^~~~
rainbow.cpp:84:12: error: 'lower_bound' was not declared in this scope
   84 |   int id = lower_bound(row1[x].begin(), row1[x].end(), y) - row1[x].begin();
      |            ^~~~~~~~~~~
rainbow.cpp: In function 'long long int count_row(int, int, int)':
rainbow.cpp:88:24: error: 'row2' was not declared in this scope
   88 |   ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
      |                        ^~~~
rainbow.cpp:9:13: error: 'pair' was not declared in this scope
    9 | #define pii pair<ll, ll>
      |             ^~~~
rainbow.cpp:88:58: note: in expansion of macro 'pii'
   88 |   ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
      |                                                          ^~~
rainbow.cpp:9:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
    9 | #define pii pair<ll, ll>
      |             ^~~~
rainbow.cpp:88:58: note: in expansion of macro 'pii'
   88 |   ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
      |                                                          ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:88:58: note: in expansion of macro 'pii'
   88 |   ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
      |                                                          ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:22: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                      ^~
rainbow.cpp:88:58: note: in expansion of macro 'pii'
   88 |   ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
      |                                                          ^~~
rainbow.cpp:88:12: error: 'lower_bound' was not declared in this scope
   88 |   ll lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
      |            ^~~~~~~~~~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:89:58: note: in expansion of macro 'pii'
   89 |   ll rid = upper_bound(row2[id].begin(), row2[id].end(), pii(R, INF)) - row2[id].begin() - 1;
      |                                                          ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:22: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                      ^~
rainbow.cpp:89:58: note: in expansion of macro 'pii'
   89 |   ll rid = upper_bound(row2[id].begin(), row2[id].end(), pii(R, INF)) - row2[id].begin() - 1;
      |                                                          ^~~
rainbow.cpp:89:12: error: 'upper_bound' was not declared in this scope
   89 |   ll rid = upper_bound(row2[id].begin(), row2[id].end(), pii(R, INF)) - row2[id].begin() - 1;
      |            ^~~~~~~~~~~
rainbow.cpp:93:3: error: 'assert' was not declared in this scope
   93 |   assert((rid - lid + 1) % 2 == 0);
      |   ^~~~~~
rainbow.cpp:3:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
    2 | #include "rainbow.h"
  +++ |+#include <cassert>
    3 | #define rep(i, a, b) for(int i = a; i <= b; i++)
rainbow.cpp: In function 'long long int count_col(int, int, int)':
rainbow.cpp:97:24: error: 'col2' was not declared in this scope
   97 |   ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
      |                        ^~~~
rainbow.cpp:9:13: error: 'pair' was not declared in this scope
    9 | #define pii pair<ll, ll>
      |             ^~~~
rainbow.cpp:97:58: note: in expansion of macro 'pii'
   97 |   ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
      |                                                          ^~~
rainbow.cpp:9:13: note: 'std::pair' is defined in header '<utility>'; did you forget to '#include <utility>'?
    9 | #define pii pair<ll, ll>
      |             ^~~~
rainbow.cpp:97:58: note: in expansion of macro 'pii'
   97 |   ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
      |                                                          ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:97:58: note: in expansion of macro 'pii'
   97 |   ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
      |                                                          ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:22: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                      ^~
rainbow.cpp:97:58: note: in expansion of macro 'pii'
   97 |   ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
      |                                                          ^~~
rainbow.cpp:97:12: error: 'lower_bound' was not declared in this scope
   97 |   ll lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
      |            ^~~~~~~~~~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:18: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                  ^~
rainbow.cpp:98:58: note: in expansion of macro 'pii'
   98 |   ll rid = upper_bound(col2[id].begin(), col2[id].end(), pii(R, INF)) - col2[id].begin() - 1;
      |                                                          ^~~
rainbow.cpp:8:12: error: expected primary-expression before 'long'
    8 | #define ll long long int
      |            ^~~~
rainbow.cpp:9:22: note: in expansion of macro 'll'
    9 | #define pii pair<ll, ll>
      |                      ^~
rainbow.cpp:98:58: note: in expansion of macro 'pii'
   98 |   ll rid = upper_bound(col2[id].begin(), col2[id].end(), pii(R, INF)) - col2[id].begin() - 1;
      |                                                          ^~~
rainbow.cpp:98:12: error: 'upper_bound' was not declared in this scope
   98 |   ll rid = upper_bound(col2[id].begin(), col2[id].end(), pii(R, INF)) - col2[id].begin() - 1;
      |            ^~~~~~~~~~~
rainbow.cpp:102:3: error: 'assert' was not declared in this scope
  102 |   assert((rid - lid + 1) % 2 == 0);
      |   ^~~~~~
rainbow.cpp:102:3: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
rainbow.cpp: In function 'int colours(int, int, int, int)':
rainbow.cpp:106:11: error: 'min' was not declared in this scope
  106 |   int u = min(ar, br), d = max(ar, br);
      |           ^~~
rainbow.cpp:108:22: error: 'd' was not declared in this scope
  108 |   ll count = area(u, d, l, r);
      |                      ^
rainbow.cpp:108:28: error: 'r' was not declared in this scope
  108 |   ll count = area(u, d, l, r);
      |                            ^