#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
const int maxn = 2e5+5;
int R, C;
struct BIT
{
vi com[maxn], pre[maxn];
BIT() {}
void update(int x, int y)
{
for (int i = x; i <= R; i += (i & (-i)))
com[i].pushb(y);
}
void build(int x)
{
sort(all(com[x]));
vector<int> cur = com[x];
com[x].clear();
for (int y : cur)
{
if (com[x].empty() || com[x].back() != y)
{
com[x].pushb(y);
pre[x].pushb(1);
}
else
pre[x].back()++;
}
for (int i = 1; i < (int)com[x].size(); i++)
pre[x][i] += pre[x][i - 1];
}
void init(vector<pii> &A)
{
sort(all(A));
A.erase(unique(all(A)), A.end());
for (auto [x, y] : A)
update(x, y);
FOR(i, 1, R+1)
build(i);
}
int query(int x, int y)
{
int res = 0;
for (int i = x; i >= 1; i -= (i & (-i)))
{
int pos = upper_bound(all(com[i]), y) - com[i].begin() - 1;
res += (pos < 0 ? 0 : pre[i][pos]);
}
return res;
}
int get(int sx, int sy, int tx, int ty)
{
return query(tx, ty) - query(tx, sy - 1) - query(sx - 1, ty) + query(sx - 1, sy - 1);
}
} g, p, cc, rw;
void init(int _R, int _C, int x, int y, int M, char *S)
{
vector<pii> row, col, G, P;
R = _R + 1;
C = _C + 1;
REP(i, M)
{
G.pushb({x, y});
REP(a, 2)
REP(b, 2)
{
P.pushb({x + a, y + b});
if (!b)
row.pushb({x + a, y + b});
if (!a)
col.pushb({x + a, y + b});
}
// cout << x << ' ' << y << '\n';
if (i == M)
break;
if (S[i] == 'N')
x--;
else if (S[i] == 'S')
x++;
else if (S[i] == 'W')
y--;
else
y++;
}
g.init(G);
p.init(P);
rw.init(row);
cc.init(col);
}
int colour(int ar, int ac, int br, int bc)
{
int V = p.get(ar + 1, ac + 1, br, bc);
int E = rw.get(ar + 1, ac, br, bc) + cc.get(ar, ac + 1, br, bc);
int total = g.get(ar, ac, br, bc), mid = 0;
if (ar + 2 <= br && ac + 2 <= bc)
mid = g.get(ar + 1, ac + 1, br - 1, bc - 1);
int F = 1;
if (V >= 1 && total == mid)
F++;
// cout << E << ' ' << V << ' ' << CC << ' ' << total << '\n';
return E - V + F - total;
}
Compilation message
rainbow.cpp: In member function 'void BIT::init(std::vector<std::pair<int, int> >&)':
rainbow.cpp:87:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
87 | for (auto [x, y] : A)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
37968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
