#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1<<18
const int SZ = MAXN;
template<class T> struct node {
T val = 0; node<T>* c[2];
node() { c[0] = c[1] = NULL; }
void upd(int ind, T v, int L = 0, int R = SZ-1) { // add v
if (L == ind && R == ind) { val += v; return; }
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->upd(ind,v,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->upd(ind,v,M+1,R);
}
val = 0; for(int i = 0; i<2; i++) if (c[i]) val += c[i]->val;
}
T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
if (hi < L || R < lo) return 0;
if (lo <= L && R <= hi) return val;
int M = (L+R)/2; T res = 0;
if (c[0]) res += c[0]->query(lo,hi,L,M);
if (c[1]) res += c[1]->query(lo,hi,M+1,R);
return res;
}
void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
if (L != R) {
int M = (L+R)/2;
if (ind <= M) {
if (!c[0]) c[0] = new node();
c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
} else {
if (!c[1]) c[1] = new node();
c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
}
}
val = (c0?c0->val:0)+(c1?c1->val:0);
}
};
template<class T> struct Node {
node<T> seg; Node* c[2];
Node() { c[0] = c[1] = NULL; }
void upd(int x, int y, T v, int L = 0, int R = SZ-1) { // add v
if (L == x && R == x) { seg.upd(y,v); return; }
int M = (L+R)/2;
if (x <= M) {
if (!c[0]) c[0] = new Node();
c[0]->upd(x,y,v,L,M);
} else {
if (!c[1]) c[1] = new Node();
c[1]->upd(x,y,v,M+1,R);
}
seg.upd(y,v); // only for addition
// seg.UPD(y,c[0]?&c[0]->seg:NULL,c[1]?&c[1]->seg:NULL);
}
T query(int x1, int x2, int y1, int y2, int L = 0, int R = SZ-1) { // query sum of rectangle
if (x1 <= L && R <= x2) return seg.query(y1,y2);
if (x2 < L || R < x1) return 0;
int M = (L+R)/2; T res = 0;
if (c[0]) res += c[0]->query(x1,x2,y1,y2,L,M);
if (c[1]) res += c[1]->query(x1,x2,y1,y2,M+1,R);
return res;
}
};
map<pair<int, int>, int> mp;
set<pair<int, int>> visited;
vector<int> trows[MAXN];
vector<int> tcols[MAXN];
vector<pair<int, int>> rows[MAXN];
vector<pair<int, int>> cols[MAXN];
Node<int> seg;
void addSquare(int a, int b){
if(visited.count({a, b})) return;
visited.insert({a, b});
mp[{a, b}]++;
mp[{a+1, b}]++;
mp[{a, b+1}]++;
mp[{a+1, b+1}]++;
trows[a].push_back(b);
tcols[b].push_back(a);
}
void init(int R, int C, int sr, int sc, int M, char *S) {
string s = S;
addSquare(sr, sc);
for(auto c : s){
if(c == 'N') sr--;
if(c == 'S') sr++;
if(c == 'W') sc--;
if(c == 'E') sc++;
addSquare(sr, sc);
}
for(auto p : mp){
if(p.second == 1) seg.upd(p.first.first, p.first.second, 1);
if(p.second == 3) seg.upd(p.first.first, p.first.second, -1);
}
for(int i = 0; i<MAXN; i++) sort(trows[i].begin(), trows[i].end());
for(int i = 0; i<MAXN; i++) sort(tcols[i].begin(), tcols[i].end());
for(int i = 0; i<MAXN; i++){
if(trows[i].empty()) continue;
int cur = trows[i][0];
for(int j = 1; j<trows[i].size(); j++){
if(trows[i][j] != trows[i][j-1]+1){
rows[i].push_back({cur, trows[i][j-1]});
cur = trows[i][j];
}
}
rows[i].push_back({cur, trows[i].back()});
}
for(int i = 0; i<MAXN; i++){
if(tcols[i].empty()) continue;
int cur = tcols[i][0];
for(int j = 1; j<tcols[i].size(); j++){
if(tcols[i][j] != tcols[i][j-1]+1){
cols[i].push_back({cur, tcols[i][j-1]});
cur = tcols[i][j];
}
}
cols[i].push_back({cur, tcols[i].back()});
}
// for(int i = 0; i<MAXN; i++){
// if(cols[i].empty()) continue;
// cout << i << endl;
// for(auto j : cols[i]) cout << j.first << " " << j.second << endl;
// cout << endl;
// }
}
int colour(int ar, int ac, int br, int bc) {
int ans = 0;
ans += seg.query(ar+1, br, ac+1, bc);
int p1, p2;
// top row
p1 = lower_bound(rows[ar].begin(), rows[ar].end(), make_pair(ac+1, -1))-rows[ar].begin();
p2 = lower_bound(rows[ar].begin(), rows[ar].end(), make_pair(bc+1, -1))-rows[ar].begin();
p1--; p2--;
if(p1 >= 0 && rows[ar][p1].second >= ac && rows[ar][p1].second < bc) ans--;
if(p2 >= 0 && rows[ar][p2].first > ac && rows[ar][p2].second >= bc) ans--;
p1++; if(p2 >= 0 && rows[ar][p2].second >= bc) p2--;
if(p1 < rows[ar].size() && rows[ar][p1].second < bc && p2 >= 0 && rows[ar][p2].first > ac) ans -= (p2-p1+1)*2;
p1 = lower_bound(rows[br].begin(), rows[br].end(), make_pair(ac+1, -1))-rows[br].begin();
p2 = lower_bound(rows[br].begin(), rows[br].end(), make_pair(bc+1, -1))-rows[br].begin();
p1--; p2--;
if(p1 >= 0 && rows[br][p1].second >= ac && rows[br][p1].second < bc) ans--;
if(p2 >= 0 && rows[br][p2].first > ac && rows[br][p2].second >= bc) ans--;
p1++; if(p2 >= 0 && rows[br][p2].second >= bc) p2--;
if(p1 < rows[br].size() && rows[br][p1].second < bc && p2 >= 0 && rows[br][p2].first > ac) ans -= (p2-p1+1)*2;
p1 = lower_bound(cols[ac].begin(), cols[ac].end(), make_pair(ar+1, -1))-cols[ac].begin();
p2 = lower_bound(cols[ac].begin(), cols[ac].end(), make_pair(br+1, -1))-cols[ac].begin();
p1--; p2--;
if(p1 >= 0 && cols[ac][p1].second >= ar && cols[ac][p1].second < br) ans--;
if(p2 >= 0 && cols[ac][p2].first > ar && cols[ac][p2].second >= br) ans--;
p1++; if(p2 >= 0 && cols[ac][p2].second >= br) p2--;
if(p1 < cols[ac].size() && cols[ac][p1].second < br && p2 >= 0 && cols[ac][p2].first > ar) ans -= (p2-p1+1)*2;
p1 = lower_bound(cols[bc].begin(), cols[bc].end(), make_pair(ar+1, -1))-cols[bc].begin();
p2 = lower_bound(cols[bc].begin(), cols[bc].end(), make_pair(br+1, -1))-cols[bc].begin();
p1--; p2--;
if(p1 >= 0 && cols[bc][p1].second >= ar && cols[bc][p1].second < br) ans--;
if(p2 >= 0 && cols[bc][p2].first > ar && cols[bc][p2].second >= br) ans--;
p1++; if(p2 >= 0 && cols[bc][p2].second >= br) p2--;
if(p1 < cols[bc].size() && cols[bc][p1].second < br && p2 >= 0 && cols[bc][p2].first > ar) ans -= (p2-p1+1)*2;
if(!visited.count({ar, ac})) ans--;
if(!visited.count({ar, bc})) ans--;
if(!visited.count({br, ac})) ans--;
if(!visited.count({br, bc})) ans--;
return -ans/4;
}
Compilation message
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:110:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int j = 1; j<trows[i].size(); j++){
| ~^~~~~~~~~~~~~~~~
rainbow.cpp:121:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int j = 1; j<tcols[i].size(); j++){
| ~^~~~~~~~~~~~~~~~
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:148:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | if(p1 < rows[ar].size() && rows[ar][p1].second < bc && p2 >= 0 && rows[ar][p2].first > ac) ans -= (p2-p1+1)*2;
| ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:156:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | if(p1 < rows[br].size() && rows[br][p1].second < bc && p2 >= 0 && rows[br][p2].first > ac) ans -= (p2-p1+1)*2;
| ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:164:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | if(p1 < cols[ac].size() && cols[ac][p1].second < br && p2 >= 0 && cols[ac][p2].first > ar) ans -= (p2-p1+1)*2;
| ~~~^~~~~~~~~~~~~~~~~
rainbow.cpp:172:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | if(p1 < cols[bc].size() && cols[bc][p1].second < br && p2 >= 0 && cols[bc][p2].first > ar) ans -= (p2-p1+1)*2;
| ~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
24940 KB |
Output is correct |
| 2 |
Correct |
18 ms |
24940 KB |
Output is correct |
| 3 |
Correct |
282 ms |
42976 KB |
Output is correct |
| 4 |
Correct |
470 ms |
64216 KB |
Output is correct |
| 5 |
Correct |
600 ms |
89532 KB |
Output is correct |
| 6 |
Correct |
543 ms |
85080 KB |
Output is correct |
| 7 |
Correct |
782 ms |
108004 KB |
Output is correct |
| 8 |
Correct |
111 ms |
28772 KB |
Output is correct |
| 9 |
Correct |
467 ms |
63836 KB |
Output is correct |
| 10 |
Correct |
602 ms |
89692 KB |
Output is correct |
| 11 |
Correct |
587 ms |
85084 KB |
Output is correct |
| 12 |
Correct |
256 ms |
50908 KB |
Output is correct |
| 13 |
Correct |
300 ms |
63708 KB |
Output is correct |
| 14 |
Correct |
433 ms |
89440 KB |
Output is correct |
| 15 |
Correct |
434 ms |
85212 KB |
Output is correct |
| 16 |
Correct |
303 ms |
45664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
24940 KB |
Output is correct |
| 2 |
Correct |
170 ms |
49172 KB |
Output is correct |
| 3 |
Correct |
144 ms |
49248 KB |
Output is correct |
| 4 |
Correct |
819 ms |
183416 KB |
Output is correct |
| 5 |
Correct |
112 ms |
43112 KB |
Output is correct |
| 6 |
Correct |
81 ms |
32100 KB |
Output is correct |
| 7 |
Incorrect |
148 ms |
37988 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
25068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
