#include "rainbow.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int N = 1 << 18, M = N * 40;
int tr[M], lv[M], rv[M], sz = 1, rt[N];
set<pair<int, int>> ss, ts;
map<int, vector<int>> mh, mv;
int lx, rx, ly, ry;
int add(int v, int p, int x, int l=0, int r=N) {
int cv = sz++;
tr[cv] = tr[v] + x;
if (r - l == 1)
lv[cv] = rv[cv] = -1;
else if (p < (l + r) / 2) {
lv[cv] = add(lv[v], p, x, l, (l + r) / 2);
rv[cv] = rv[v];
}
else {
lv[cv] = lv[v];
rv[cv] = add(rv[v], p, x, (l + r) / 2, r);
}
return cv;
}
int sum(int v, int cl, int cr, int l=0, int r=N) {
if (v == -1 || cr <= l || r <= cl)
return 0;
if (cl <= l && r <= cr)
return tr[v];
return sum(lv[v], cl, cr, l, (l + r) / 2) + sum(rv[v], cl, cr, (l + r) / 2, r);
}
void init(int r, int c, int sr, int sc, int m, char *s) {
m = 0;
lx = rx = sr;
ly = ry = sc;
ss.insert({sr, sc});
rep(i, m) {
if (s[i] == 'N') sr--;
else if (s[i] == 'S') sr++;
else if (s[i] == 'W') sc--;
else sc++;
lx = min(lx, sr);
rx = max(rx, sr);
ly = min(ly, sc);
ry = max(ry, sc);
ss.insert({sr, sc});
}
for (auto &p : ss) {
// cout << p.first << ' ' << p.second << '\n';
ts.insert(p);
if (p.first > 1) {
ts.insert({p.first - 1, p.second});
if (p.second > 1)
ts.insert({p.first - 1, p.second - 1});
}
if (p.second > 1)
ts.insert({p.first, p.second - 1});
}
int crt = 0, ls = 0;
for (auto &p : ts) {
while (ls < p.first)
rt[ls++] = crt;
int val = -1;
if (ss.count(p)) {
val += 1;
if (!ss.count({p.first, p.second + 1}))
mh[p.first].push_back(p.second);
if (!ss.count({p.first + 1, p.second}))
mv[p.second].push_back(p.first);
}
else {
if (ss.count({p.first, p.second + 1}))
val++;
if (ss.count({p.first + 1, p.second}))
val++;
}
crt = add(crt, p.second, val);
}
while (ls < N)
rt[ls++] = crt;
for (auto &p : mh)
sort(all(p.second));
for (auto &p : mv)
sort(all(p.second));
}
int colour(int ar, int ac, int br, int bc) {
ll ans = 1 + sum(rt[br - 1], ac, bc) - sum(rt[ar - 1], ac, bc);
if (mh.count(br))
ans += lower_bound(all(mh[br]), bc) - lower_bound(all(mh[br]), ac);
if (mv.count(bc))
ans += lower_bound(all(mv[bc]), br) - lower_bound(all(mv[bc]), ar);
if (ss.count({br, ac}))
ans--;
if (ss.count({ar, bc}))
ans--;
if (ss.count({br, bc}))
ans++;
if (ar < lx && rx < br && ac < ly && ry < bc)
ans++;
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1408 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
