#include "rainbow.h"
#include <bits/stdc++.h>
#define sz(v) (int)(v).size()
using namespace std;
const int MXn = 2e5 + 5;
const int dx[] = {1, 0, 1};
const int dy[] = {0, 1, 1};
int n, m;
struct PST {
vector<int> val, idL, idR;
void resiz(int s) {
val.resize(s + 3);
idL.resize(s + 3);
idR.resize(s + 3);
}
int no = 0;
int build(int l = 1, int r = n) {
int cur = ++no;
val[cur] = 0;
if (l == r) return cur;
int mid = (l + r) >> 1;
idL[cur] = build(l, mid);
idR[cur] = build(mid + 1, r);
return cur;
}
int update(int i, int v, int oID, int l = 1, int r = n) {
// if (l == 1 && r == m) cerr << i << ' ' << v << '\n';
int nod = ++no;
if (l == r) {
val[nod] = val[oID] + v;
return nod;
}
int mid = (l + r) >> 1;
if (i <= mid) {
idL[nod] = update(i, v, idL[oID], l, mid);
idR[nod] = idR[oID];
} else {
idL[nod] = idL[oID];
idR[nod] = update(i, v, idR[oID], mid + 1, r);
}
val[nod] = val[idL[nod]] + val[idR[nod]];
return nod;
}
int get(int Lf, int Rt, int id, int l = 1, int r = n) {
if (Lf <= l && r <= Rt) {
// cerr << id << ' ' << l << ' ' << r << ' ' << val[id] << '\n';
return val[id];
}
int mid = (l + r) >> 1;
int res = 0;
if (Lf <= mid) res += get(Lf, Rt, idL[id], l, mid);
if (Rt > mid) res += get(Lf, Rt, idR[id], mid + 1, r);
return res;
}
} T[4];
int root[4][MXn];
bool onboard(int x, int y) {
return 1 <= x && x <= n && 1 <= y && y <= m;
}
vector<int> river[MXn], v1[MXn], v2[MXn], v3[MXn];
void add(int sr, int sc) {
river[sc].emplace_back(sr);
if (sc > 1) v1[sc - 1].emplace_back(sr);
v1[sc].emplace_back(sr);
if (sr > 1) v2[sc].emplace_back(sr - 1);
v2[sc].emplace_back(sr);
v3[sc].emplace_back(sr);
for (int k = 0; k < 3; k++) {
int xx = dx[k] + sr, yy = dy[k] + sc;
if (onboard(xx, yy)) v3[yy].emplace_back(xx);
}
}
void init(int R, int C, int sr, int sc, int M, char *S) {
n = R, m = C;
add(sr, sc);
for (int i = 0; i < M; i++) {
if (S[i] == 'N') sr--;
if (S[i] == 'S') sr++;
if (S[i] == 'W') sc--;
if (S[i] == 'E') sc++;
// cerr << "(" << sr << ' ' << sc << ")\n";
add(sr, sc);
}
vector<int> siz(4, 0);
for (int c = 1; c <= C; c++) {
sort(begin(river[c]), end(river[c]));
river[c].resize(unique(begin(river[c]), end(river[c])) - river[c].begin());
siz[0] += sz(river[c]);
sort(begin(v1[c]), end(v1[c]));
v1[c].resize(unique(begin(v1[c]), end(v1[c])) - v1[c].begin());
siz[1] += sz(v1[c]);
sort(begin(v2[c]), end(v2[c]));
v2[c].resize(unique(begin(v2[c]), end(v2[c])) - v2[c].begin());
siz[2] += sz(v2[c]);
sort(begin(v3[c]), end(v3[c]));
v3[c].resize(unique(begin(v3[c]), end(v3[c])) - v3[c].begin());
siz[3] += sz(v3[c]);
}
// cerr << '\n';
// T[0].resize((1 << 19) + sz[0] * 19);
// T[1].resize((1 << 19) + sz[1] * 19);
// T[2].resize((1 << 19) + sz[2] * 19);
// T[3].resize((1 << 19) + sz[3] * 19);
for (int t = 0; t < 4; t++) {
T[t].resiz((1 << 19) + siz[t] * 19);
root[t][0] = T[t].build();
}
// int ro = T[0].update(4, 1, root[0][0]);
// cerr << T[0].get(3, 4, ro) << '\n';
for (int c = 1; c <= C; c++) {
root[0][c] = root[0][c - 1];
root[1][c] = root[1][c - 1];
root[2][c] = root[2][c - 1];
root[3][c] = root[3][c - 1];
for (int r: river[c]) {
// cerr << r << ' ';
root[0][c] = T[0].update(r, 1, root[0][c]);
}
for (int r: v1[c]) {
root[1][c] = T[1].update(r, 1, root[1][c]);
}
for (int r: v2[c]) {
root[2][c] = T[2].update(r, 1, root[2][c]);
}
for (int r: v3[c]) {
root[3][c] = T[3].update(r, 1, root[3][c]);
}
// cerr << "---\n" << T[0].get(3, 4, root[0][c]) << '\n';
}
// cerr << '\n';
}
int colour(int ar, int ac, int br, int bc) {
long long V = (br - ar + 1) * (bc - ac + 1) - (T[0].get(ar, br, root[0][bc]) - T[0].get(ar, br, root[0][ac - 1]));
long long E = (bc - ac) * (br - ar + 1) - (T[1].get(ar, br, root[1][bc - 1]) - T[1].get(ar, br, root[1][ac - 1])) + (bc - ac + 1) * (br - ar) - (T[2].get(ar, br - 1, root[2][bc]) - T[2].get(ar, br - 1, root[2][ac - 1]));
long long F = 0;
if (ar < br) F = (br - ar) * (bc - ac) - (T[3].get(ar + 1, br, root[3][bc]) - T[3].get(ar + 1, br, root[3][ac]));
// cerr << V << ' ' << E << ' ' << F << '\n';
// cerr << V << ' ' << T[0].get(ar, br, root[0][bc]) << ' ' << T[0].get(ar, br, root[0][ac - 1]) << '\n';
return V - E + F;
// return 0;
}
// static int R, C, M, Q;
// static int sr, sc;
// static char S[100000 + 5];
//
// int main() {
// scanf("%d %d %d %d", &R, &C, &M, &Q);
// scanf("%d %d", &sr, &sc);
// if (M > 0) {
// scanf(" %s ", S);
// }
//
// init(R, C, sr, sc, M, S);
//
// int query;
// for (query = 0; query < Q; query++) {
// int ar, ac, br, bc;
// scanf("%d %d %d %d", &ar, &ac, &br, &bc);
// printf("%d\n", colour(ar, ac, br, bc));
// }
//
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
718 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
725 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
676 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
718 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
718 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
