/** I can do this all day **/
#include <bits/stdc++.h>
#include "rainbow.h"
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define Mp make_pair
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;
ll pw(ll a , ll b, ll M) { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }
struct segment
{
segment () {}
vector < int > seg[N << 2], id[N << 2];
void add(int p, int x, int v = 1, int tl = 0, int tr = N - 1)
{
if(p > tr || p < tl) return;
if(tl == tr)
{
seg[v].push_back(x);
return;
}
int mid = (tl + tr) >> 1;
add(p, x, v << 1, tl, mid);
add(p, x, v << 1 | 1, mid + 1, tr);
}
void Merge(int v)
{
int n = SZ(seg[v << 1]), m = SZ(seg[v << 1 | 1]), i = 0, j = 0, k = 0;
id[v].resize(n + m + 1, 0);
seg[v].resize(n + m);
while(j < n || k < m)
{
if(j < n && (k == m || seg[v << 1][j] < seg[v << 1 | 1][k]))
{
seg[v][i] = seg[v << 1][j];
id[v][i + 1] = id[v][i] + 1;
j ++;
}
else
{
seg[v][i] = seg[v << 1 | 1][k];
id[v][i + 1] = id[v][i];
k ++;
}
i ++;
}
}
void build(int v = 1, int tl = 0, int tr = N - 1)
{
if(tl == tr)
{
sort(all(seg[v]));
seg[v].resize(unique(all(seg[v])) - seg[v].begin());
return;
}
int mid = (tl + tr) >> 1;
build(v << 1, tl, mid);
build(v << 1 | 1, mid + 1, tr);
Merge(v);
}
int get(int l, int r, int x, int v = 1, int tl = 0, int tr = N - 1)
{
if(l > tr || r < tl || l > r) return 0;
if(l <= tl && tr <= r)
{
return x;
}
int mid = (tl + tr) >> 1;
return get(l, r, id[v][x], v << 1, tl, mid) + get(l, r, x - id[v][x], v << 1 | 1, mid + 1, tr);
}
int ask(int l, int r, int L, int R)
{
if(l > r || L > R) return 0;
int x = upper_bound(all(seg[1]), R) - seg[1].begin();
int x2 = upper_bound(all(seg[1]), L - 1) - seg[1].begin();
return get(l, r, x) - get(l, r, x2);
}
} S1, S2, S3, S4; /// S1 -> bala chap 2 * 2
/// S2 -> bala chap 1 * 2
/// S3 -> bala chap 2 * 1
/// S4 -> bala chap 1 * 1
map < pii, int > mp;
int mnR, mnC, mxR, mxC;
void init(int R, int C, int sr, int sc, int M, char *S)
{
char* s = S;
int a = sr, b = sc, n = M;
vector < pii > points;
mnR = mxR = a;
mnC = mxC = b;
points.push_back(Mp(a, b));
for(int i = 0; i < n; i ++)
{
if(s[i] == 'N')
{
a --;
}
if(s[i] == 'S')
{
a ++;
}
if(s[i] == 'E')
{
b ++;
}
if(s[i] == 'W')
{
b --;
}
points.push_back(Mp(a, b));
}
for(auto x : points)
{
mp[x] = 1;
mnR = min(mnR, x.F);
mxR = max(mxR, x.F);
mnC = min(mnC, x.S);
mxC = max(mxC, x.S);
}
for(auto x : points)
{
if(mp[Mp(x.F + 1, x.S)] == 1 && mp[Mp(x.F + 1, x.S + 1)] == 1 && mp[Mp(x.F, x.S + 1)]== 1)
{
S1.add(x.F, x.S);
}
if(mp[Mp(x.F + 1, x.S)] == 1)
{
S2.add(x.F, x.S);
}
if(mp[Mp(x.F, x.S + 1)] == 1)
{
S3.add(x.F, x.S);
}
S4.add(x.F, x.S);
}
S1.build();
S2.build();
S3.build();
S4.build();
}
int colour(int ar, int ac, int br, int bc) /// V + F - M = 1 + C -> C = tedad moalefe haye graph mosatah
{ /// M - V + C + 1 = F -> toye soale ma F - 1 ro mikhaim C = 2 age doresh tohi bashe
int r1 = ar, c1 = ac, r2 = br, c2 = bc;
int V = 0, M = 0;
V += S4.ask(r1, r2, c1, c2);
M += S3.ask(r1, r2, c1, c2 - 1);
M += S2.ask(r1, r2 - 1, c1, c2);
M += S4.ask(r1, r2, c1, c1);
M += S4.ask(r1, r2, c2, c2);
M += S4.ask(r1, r1, c1, c2);
M += S4.ask(r2, r2, c1, c2);
int tot = M - V + 1, ret = 0;
ret += S1.ask(r1, r2 - 1, c1, c2 - 1);
ret += S2.ask(r1, r2 - 1, c1, c1);
ret += S2.ask(r1, r2 - 1, c2, c2);
ret += S3.ask(r1, r1, c1, c2 - 1);
ret += S3.ask(r2, r2, c1, c2 - 1);
ret += mp[Mp(r1, c1)];
ret += mp[Mp(r1, c2)];
ret += mp[Mp(r2, c1)];
ret += mp[Mp(r2, c2)];
if(mnR > r1 && mxR < r2 && mnC > c1 && mxC < c2) tot ++;
return tot - ret;
}
/*int main()
{
char C[10] = "NWESSWEWS";
init(6, 4, 3, 3, 9, C);
printf("%d\n", colour(1, 2, 5, 3));
return 0;
}
*/
/** test corner cases(n = 1?) watch for overflow or minus indices **/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
175744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
175724 KB |
Output is correct |
| 2 |
Correct |
170 ms |
175724 KB |
Output is correct |
| 3 |
Correct |
1444 ms |
210772 KB |
Output is correct |
| 4 |
Correct |
1687 ms |
228496 KB |
Output is correct |
| 5 |
Correct |
1744 ms |
228592 KB |
Output is correct |
| 6 |
Correct |
1473 ms |
229200 KB |
Output is correct |
| 7 |
Correct |
1769 ms |
211240 KB |
Output is correct |
| 8 |
Correct |
943 ms |
190796 KB |
Output is correct |
| 9 |
Correct |
1743 ms |
226132 KB |
Output is correct |
| 10 |
Correct |
1746 ms |
225880 KB |
Output is correct |
| 11 |
Correct |
1688 ms |
225740 KB |
Output is correct |
| 12 |
Correct |
796 ms |
215300 KB |
Output is correct |
| 13 |
Correct |
782 ms |
217952 KB |
Output is correct |
| 14 |
Correct |
793 ms |
217884 KB |
Output is correct |
| 15 |
Correct |
804 ms |
216856 KB |
Output is correct |
| 16 |
Correct |
1440 ms |
217644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
175724 KB |
Output is correct |
| 2 |
Correct |
332 ms |
218080 KB |
Output is correct |
| 3 |
Correct |
418 ms |
224608 KB |
Output is correct |
| 4 |
Correct |
389 ms |
222304 KB |
Output is correct |
| 5 |
Correct |
330 ms |
210960 KB |
Output is correct |
| 6 |
Correct |
327 ms |
192480 KB |
Output is correct |
| 7 |
Incorrect |
363 ms |
206108 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
175744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
175744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
