#include "rainbow.h"
//#define _GLIBCXX_DEBUG
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
template<typename T>
bool ckmn(T &x, T y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<typename T>
bool ckmx(T &x, T y) {
if (x < y) {
x = y;
return true;
}
return false;
}
int bit(int x, int b) {
return (x >> b) & 1;
}
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
template<typename T>
void make_uniq(vector<T> &v) {
sort(all(v));
v.resize(unique(all(v)) - begin(v));
}
struct Fenwick {
vector<vector<ll>> t;
vector<vector<int>> yy;
int n;
Fenwick() = default;
void init(int a) {
n = a;
yy.resize(n);
t.resize(n);
}
void fake_add(int x, int y) {
for (int i = x; i < n; i |= (i + 1))
yy[i].pb(y);
}
void build() {
for (int i = 0; i < n; ++i) {
make_uniq(yy[i]);
t[i].resize(sz(yy[i]) + 2);
}
}
void add(int x, int y) {
for (int i = x; i < n; i |= (i + 1))
for (int j = lower_bound(all(yy[i]), y) - begin(yy[i]); j < sz(yy[i]); j |= (j + 1))
++t[i][j];
}
ll get(int x, int y) {
ll ans = 0;
for (int i = x; i > -1; i = ((i + 1) & i) - 1)
for (int j = upper_bound(all(yy[i]), y) - begin(yy[i]) - 1; j > -1; j = ((j + 1) & j) - 1)
ans += t[i][j];
return ans;
}
ll get(int x1, int y1, int x2, int y2) {
return get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
}
};
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
int n, m;
vector<pair<int, int>> yy;
Fenwick fx, fy, fv, cv;
int mnx = infI, mny = infI, mxx = -infI, mxy = -infI;
auto here = [](int x, int y) -> bool {
auto it = lower_bound(all(yy), mp(x, y));
if (it == end(yy)) return false;
return (*it) == mp(x, y);
};
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
--sr, --sc;
fx.init(n), fy.init(n), fv.init(n), cv.init(n);
yy = {{sr, sc}};
for (int i = 0; i < M; ++i) {
if (S[i] == 'N') --sr;
else if (S[i] == 'S') ++sr;
else if (S[i] == 'W') --sc;
else ++sc;
yy.emplace_back(sr, sc);
}
make_uniq(yy);
vector<pii > pv, px, py, cvv;
for (auto [x, y]: yy) { ;
pv.emplace_back(x, y);
ckmx(mxx, x);
ckmx(mxy, y);
ckmn(mnx, x);
ckmn(mny, y);
for (int i = 0; i < 2; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (here(nx, ny)) {
if (nx == x) {
px.emplace_back(x, y);
} else {
py.emplace_back(x, y);
}
}
}
if (here(x + 1, y) && here(x, y + 1) && here(x + 1, y + 1)) {
cvv.emplace_back(x, y);
}
}
make_uniq(pv), make_uniq(px), make_uniq(py), make_uniq(cvv);
for (auto [x, y]: pv)
fv.fake_add(x, y);
for (auto [x, y]: px)
fx.fake_add(x, y);
for (auto [x, y]: py)
fy.fake_add(x, y);
for (auto [x, y]: cvv)
cv.fake_add(x, y);
fv.build(), fx.build(), fy.build(), cv.build();
for (auto [x, y]: pv)
fv.add(x, y);
for (auto [x, y]: px)
fx.add(x, y);
for (auto [x, y]: py)
fy.add(x, y);
for (auto [x, y]: cvv)
cv.add(x, y);
assert(sz(pv) == sz(yy));
assert(fv.get(n - 1, m - 1) == sz(yy));
}
int colour(int ar, int ac, int br, int bc) {
int x1 = ar, y1 = ac, x2 = br, y2 = bc;
--x1, --y1;
--x2, --y2;
bool f2 = (mnx > x1 && mny > y1 && mxx < x2 && mxy < y2);
int cnt_in = fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
int cnt_stup = 0;
for (auto [x, y]: yy) {
if (x1 < x && x < x2 && y1 < y && y < y2) ++cnt_stup;
}
assert(cnt_in == cnt_stup);
bool f1 = cnt_in == (ll) sz(yy);
if (!f2) {
// assert(!f1);
}
ll C = 1 + bool(fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1) == (ll) sz(yy));
ll E = (x2 - x1 + 2) * 2 + (y2 - y1 + 2) * 2;
E += fx.get(x1, y1, x2, y2 - 1) + fy.get(x1, y1, x2 - 1, y2);
E += fv.get(x1, y2, x2, y2);
E += fv.get(x1, y1, x2, y1);
E += fv.get(x1, y1, x1, y2);
E += fv.get(x2, y1, x2, y2);
ll V = (x2 - x1 + 2) * 2LL + (y2 - y1 + 2) * 2LL + fv.get(x1, y1, x2, y2);
ll cnt_squares = fx.get(x1, y1, x1, y2 - 1) + fx.get(x2, y1, x2, y2 - 1) + fy.get(x1, y1, x2 - 1, y1) +
fy.get(x1, y2, x2 - 1, y2);
// .-.
// | | <---- counted this F extra time
// O-O
ll cnt_on_corners = here(x1, y1) + here(x1, y2) + here(x2, y2) + here(x2, y1);
// .-.
// | | <--- nums of Os, so we counted this F extra 1 time
// .-O
ll U = cv.get(x1, y1, x2 - 1, y2 - 1) + cnt_on_corners + cnt_squares;
ll F = C + 1 + E - V;
ll ans = F - U - 1;
assert(ans >= 0);
return (int) ans;
}
Compilation message
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:217:10: warning: unused variable 'f1' [-Wunused-variable]
217 | bool f1 = cnt_in == (ll) sz(yy);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
