This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include "bits/stdc++.h"
using namespace std;
int N, M;
typedef pair <int, int> pii;
struct Container {
vector <int> t[200010 * 4];
void insert(int x, int y, int c, int b, int e) {
if(b == e) {
t[c].emplace_back(y);
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
if(x <= m) insert(x, y, l, b, m);
else insert(x, y, r, m + 1, e);
}
void build(int c, int b, int e) {
if(b == e) {
sort(t[c].begin(), t[c].end());
return ;
}
int m = (b + e) >> 1;
int l = c << 1;
int r = l + 1;
build(l, b, m);
build(r, m + 1, e);
merge(t[l].begin(), t[l].end(), t[r].begin(), t[r].end(), back_inserter(t[c]));
}
int count(int x, int y, int p, int q, int c, int b, int e) {
if(x <= b && e <= y) {
return upper_bound(t[c].begin(), t[c].end(), q) - lower_bound(t[c].begin(), t[c].end(), p);
}
if(y < b || e < x) return 0;
int l = c << 1;
int r = l + 1;
int m = (b + e) >> 1;
return count(x, y, p, q, l, b, m) + count(x, y, p, q, r, m + 1, e);
}
int count(int x, int y, int p, int q) {
if(x > y || p > q) return 0;
return count(x, y, p, q, 1, 1, N);
}
void insert(int x, int y) {
insert(x, y, 1, 1, N);
}
void build() {
build(1, 1, N);
}
} E1, E2, V, F;
int lx, rx, ly, ry;
void init(int R, int C, int sr, int sc, int len, char *S) {
N = R;
M = C;
vector <pii> u;
u.emplace_back(sr, sc);
// int len = strlen();
for(int i = 0; i < len; i++) {
if(S[i] == 'N') --sr;
else if (S[i] == 'S') ++sr;
else if (S[i] == 'W') --sc;
else ++sc;
u.emplace_back(sr, sc);
}
lx = N, ly = M;
rx = 1, ry = 1;
for(auto i : u) {
lx = min(lx, i.first);
ly = min(ly, i.second);
rx = max(rx, i.first);
ry = max(ry, i.second);
}
set <pii> s;
for(auto i : u) {
s.emplace(i.first, i.second);
s.emplace(i.first - 1, i.second);
s.emplace(i.first, i.second - 1);
s.emplace(i.first - 1, i.second - 1);
}
for(auto i : s) {
if(0 < i.first && 0 < i.second) {
F.insert(i.first, i.second);
}
}
s.clear();
for(auto i : u) {
s.emplace(i.first - 1, i.second);
s.emplace(i.first, i.second);
}
for(auto i : s) {
if(0 < i.first && 0 < i.second) {
E1.insert(i.first, i.second);
}
}
s.clear();
for(auto i : u) {
s.emplace(i.first, i.second - 1);
s.emplace(i.first, i.second);
}
for(auto i : s) {
if(0 < i.first && 0 < i.second) {
E2.insert(i.first, i.second);
}
}
s.clear();
for(auto i : u) {
s.emplace(i.first, i.second);
}
for(auto i : s) {
V.insert(i.first, i.second);
}
s.clear();
F.build();
V.build();
E1.build();
E2.build();
}
int colour(int ar, int ac, int br, int bc) {
long long cnt = 0;
int row = br - ar + 1;
int col = bc - ac + 1;
long long e = 0;
e += 1LL * (row - 1) * col;
e += 1LL * row * (col - 1);
e -= E1.count(ar, br - 1, ac, bc);
e -= E2.count(ar, br, ac, bc - 1);
long long v = 0;
v += 1LL * row * col;
v -= V.count(ar, br, ac, bc);
long long f = 1;
f += 1LL * (row - 1) * (col - 1);
f -= F.count(ar, br - 1, ac, bc - 1);
if(ar < lx && rx < br) {
if(ac < ly && ry < bc) {
f += 1;
}
}
cnt = v - e + f - 1;
return cnt;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |