//#define wiwihorz
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rainbow.h"
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#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 ceil(a, b) ((a + b - 1) / (b))
#define all(x) x.begin(), x.end()
#define INF 1000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#define treap tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#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 {
int n, m, sr, sc, op;
char s[200000];
vector<vector<int>> 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_(signed _n, signed _m, signed _sr, signed _sc, signed _op, char* _s) {
n = _n, m = _m, sr = _sr, sc = _sc, op = _op, s = _s;
row1.assign(n + 1, vector<int>());
row2.assign(n + 1, vector<pii>());
col1.assign(m + 1, vector<int>());
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) {
print(cur.x, cur.y);
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());
int 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());
int 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;
}
int area(int u, int d, int l, int r) {
int 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;
}
int count_row(int id, int L, int R) {
print(id, L, R, "r");
for(auto i : row2[id]) print(i.x, i.y);
int lid = lower_bound(row2[id].begin(), row2[id].end(), pii(L, -INF)) - row2[id].begin();
int 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 ++;
print(lid, rid);
assert((rid - lid + 1) % 2 == 0);
return (rid - lid + 1) / 2;
}
int count_col(int id, int L, int R) {
print(id, L, R, "c");
for(auto i : col2[id]) print(i.x, i.y);
int lid = lower_bound(col2[id].begin(), col2[id].end(), pii(L, -INF)) - col2[id].begin();
int 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;
}
signed colours(signed ar, signed ac, signed br, signed bc) {
int u = min(ar, br), d = max(ar, br);
int l = min(ac, bc), r = max(ac, bc);
print(u, d, l, r);
int count = area(u, d, l, r);
print(count);
if(!count) return 1;
if(count == ((d - u + 1) * (r - l + 1))) return 0;
int 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);
print(ans);
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; string 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:7: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
7 | #pragma loop-opt(on)
|
rainbow.cpp: In function 'void solver1::init_(int, int, int, int, int, char*)':
rainbow.cpp:48:51: error: incompatible types in assignment of 'char*' to 'char [200000]'
48 | n = _n, m = _m, sr = _sr, sc = _sc, op = _op, s = _s;
| ~~^~~~
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:57:4: note: in expansion of macro 'print'
57 | print(cur.x, cur.y);
| ^~~~~
rainbow.cpp: In function 'long long int solver1::area(long long int, long long int, long long int, long long int)':
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:96:4: note: in expansion of macro 'print'
96 | print(i, L, R);
| ^~~~~
rainbow.cpp:34:21: warning: statement has no effect [-Wunused-value]
34 | #define vprint(...) 0
| ^
rainbow.cpp:97:4: note: in expansion of macro 'vprint'
97 | vprint(all(row1[i]));
| ^~~~~~
rainbow.cpp: In function 'bool solver1::occ(long long int, long long int)':
rainbow.cpp:104:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | return id < row1[x].size() && row1[x][id] == y;
| ~~~^~~~~~~~~~~~~~~~
rainbow.cpp: In function 'long long int solver1::count_row(long long int, long long int, long long int)':
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:107:3: note: in expansion of macro 'print'
107 | print(id, L, R, "r");
| ^~~~~
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:108:26: note: in expansion of macro 'print'
108 | for(auto i : row2[id]) print(i.x, i.y);
| ^~~~~
rainbow.cpp:113:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if(rid + 1 < row2[id].size() && row2[id][rid + 1].y == row2[id][rid].y) rid ++;
| ~~~~~~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:114:3: note: in expansion of macro 'print'
114 | print(lid, rid);
| ^~~~~
rainbow.cpp: In function 'long long int solver1::count_col(long long int, long long int, long long int)':
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:119:3: note: in expansion of macro 'print'
119 | print(id, L, R, "c");
| ^~~~~
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:120:26: note: in expansion of macro 'print'
120 | for(auto i : col2[id]) print(i.x, i.y);
| ^~~~~
rainbow.cpp:125:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | if(rid + 1 < col2[id].size() && col2[id][rid + 1].y == col2[id][rid].y) rid ++;
| ~~~~~~~~^~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int solver1::colours(int, int, int, int)':
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:132:3: note: in expansion of macro 'print'
132 | print(u, d, l, r);
| ^~~~~
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:134:3: note: in expansion of macro 'print'
134 | print(count);
| ^~~~~
rainbow.cpp:33:20: warning: statement has no effect [-Wunused-value]
33 | #define print(...) 0
| ^
rainbow.cpp:139:3: note: in expansion of macro 'print'
139 | print(ans);
| ^~~~~
