#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 200005
#define lowbit(x) (x&-x)
#include"rainbow.h"
struct dbit{
unordered_map<int,int> mp[N];
int n,m;
void init(int _n,int _m){
n = _n,m = _m;
for(int i=1;i<=n;i++) mp[i].clear();
}
void add(int x,int y,int c){
for(;x<n;x+=lowbit(x)) for(;y<m;y+=lowbit(y))
mp[x][y] += c;
}
int qur(int x,int y){
int r = 0;
for(;x;x-=lowbit(x)) for(;y;y-=lowbit(y)){
auto it = mp[x].find(y);
if(it != mp[x].end()) r += it->second;
}
return r;
}
int squr(int x,int y,int xx,int yy){
if(xx<x||yy<y) return 0;
//cout << x << ' ' << xx << ' ' << y << ' ' << yy << '\n';
return qur(xx,yy) - qur(x-1,yy) - qur(xx,yy-1) + qur(x-1,y-1);
}
}b11,b21,b12,b22;
set<pair<int,int> > s;
void init(int R,int C,int sr,int sc,int M,char* S){
b11.init(R,C);
b21.init(R,C);
b12.init(R,C);
b22.init(R,C);
s.clear();
s.insert({sr,sc});
for(int j=0;j<M;j++){
char &i = S[j];
if(i == 'N') sr--;
else if(i == 'E') sc++;
else if(i == 'W') sc--;
else if(i == 'S') sr++;
s.insert({sr,sc});
}
vector<pair<int,int> > v(s.begin(),s.end());
for(auto i : v){
b11.add(i.first,i.second,1);
int cnt = 0;
if(s.find({i.first+1,i.second}) != s.end())
b21.add(i.first,i.second,1),cnt++; //vert
if(s.find({i.first,i.second+1}) != s.end())
b12.add(i.first,i.second,1),cnt++; //hori
if(s.find({i.first+1,i.second+1}) != s.end()) cnt++;
if(cnt == 3) b22.add(i.first,i.second,1);
}
}
int colour(int ar,int ac,int br,int bc){
int v11 = (br-ar+bc-ac+4)*2 + b11.squr(ar,ac,br,bc);
int v21 = (br-ar+2)*2 + b21.squr(ar,ac,br-1,bc) + b11.squr(br,ac,br,bc) + b11.squr(ar,ac,ar,bc);
int v12 = (bc-ac+2)*2 + b12.squr(ar,ac,br,bc-1) + b11.squr(ar,bc,br,bc) + b11.squr(ar,ac,br,ac);
int v22 = b22.squr(ar,ac,br-1,bc-1) +
b12.squr(ar,ac,ar,bc-1) + b12.squr(br,ac,br,bc-1) +
b21.squr(ar,ac,br-1,ac) + b21.squr(ar,bc,br-1,bc);
if(s.find({ar,ac}) != s.end()) v22++;
if(s.find({br,ac}) != s.end()) v22++;
if(s.find({ar,bc}) != s.end()) v22++;
if(s.find({br,bc}) != s.end()) v22++;
return v21 + v12 - v11 - v22 + 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
44408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
44152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
44148 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
44408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
44408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
