#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cout << #x << " :: " << x << '\n'
#define _ << " " <<
#define FOR(i,a,b) for (int i=(a); i<=(b); ++i)
#define RFOR(i,a,b) for (int i=(a); i>=(b); --i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
struct node {
int s, e, m; vector<int> v;
node *l, *r;
node(int s, int e): s(s), e(e), m((s+e)/2) {
if (s != e) l = new node(s,m), r = new node(m+1,e);
}
void add(int x, int z) {
if (s == e) { v.push_back(z); return; }
else if (x <= m) l->add(x,z);
else r->add(x,z);
}
vector<int>& build() {
if (s != e) {
auto a = l->build(), b = r->build();
for (int i = 0, j = 0; i < SZ(a) || j < SZ(b); ) {
if (i < SZ(a) && (j == SZ(b) || a[i] < b[j])) v.push_back(a[i++]);
else v.push_back(b[j++]);
}
}
return v;
}
int query(int x, int y, int a, int b) {
if (x > y || a > b) return 0;
if (s == x && e == y) { return lower_bound(ALL(v),b+1)-lower_bound(ALL(v),a); }
if (y <= m) return l->query(x,y,a,b);
if (x > m) return r->query(x,y,a,b);
return l->query(x,m,a,b) + r->query(m+1,y,a,b);
}
} *grid, *horz, *vert, *face;
int mr[2];
int mc[2];
void init(int R, int C, int sr, int sc, int M, char *S) {
grid = new node(1,R+1);
horz = new node(1,R+1);
vert = new node(1,R+1);
face = new node(1,R+1);
mr[0] = mr[1] = sr;
mc[0] = mc[1] = sc;
using ii = pair<int,int>;
vector<ii> gset, vset, hset, fset;
gset.emplace_back(sr,sc);
vset.emplace_back(sr,sc+1);
hset.emplace_back(sr+1,sc);
fset.emplace_back(sr+1,sc+1);
FOR(i,0,M-1){
switch (S[i]) {
case 'N':
--sr;
break;
case 'S':
++sr;
break;
case 'E':
++sc;
break;
case 'W':
--sc;
break;
}
vset.emplace_back(sr,sc);
gset.emplace_back(sr,sc);
vset.emplace_back(sr,sc);
vset.emplace_back(sr,sc+1);
hset.emplace_back(sr,sc);
hset.emplace_back(sr+1,sc);
fset.emplace_back(sr,sc);
fset.emplace_back(sr+1,sc);
fset.emplace_back(sr,sc+1);
fset.emplace_back(sr+1,sc+1);
mr[0] = min(mr[0],sr); mr[1] = max(mr[1],sr);
mc[0] = min(mc[0],sc); mc[1] = max(mc[0],sc);
}
sort(ALL(gset)); gset.resize(unique(ALL(gset))-gset.begin());
sort(ALL(hset)); hset.resize(unique(ALL(hset))-hset.begin());
sort(ALL(vset)); vset.resize(unique(ALL(vset))-vset.begin());
sort(ALL(fset)); fset.resize(unique(ALL(fset))-fset.begin());
for (auto& x : gset) grid->add(x.first,x.second);
for (auto& x : hset) horz->add(x.first,x.second);
for (auto& x : vset) vert->add(x.first,x.second);
for (auto& x : fset) face->add(x.first,x.second);
grid->build();
horz->build();
vert->build();
face->build();
}
int colour(int ar, int ac, int br, int bc) {
long long v = (long long)(br-ar+1)*(bc-ac+1) - grid->query(ar,br,ac,bc);
if (v == 0) return 0;
long long e = (long long)(br-ar)*(bc-ac+1) - horz->query(ar+1,br,ac,bc)
+ (long long)(br-ar+1)*(bc-ac) - vert->query(ar,br,ac+1,bc);
long long f = (long long)(br-ar)*(bc-ac) - face->query(ar+1,br,ac+1,bc) + 1;
//TRACE(v _ e _ f);
return v-e+f-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
251 ms |
155180 KB |
Output is correct |
| 3 |
Correct |
372 ms |
180436 KB |
Output is correct |
| 4 |
Correct |
334 ms |
175572 KB |
Output is correct |
| 5 |
Correct |
288 ms |
156748 KB |
Output is correct |
| 6 |
Correct |
199 ms |
118736 KB |
Output is correct |
| 7 |
Incorrect |
227 ms |
128728 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
