// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define pb push_back
#ifndef safar
#include "rainbow.h"
#endif
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> pii;
template<typename T>
void Unique(vector<T> &V){
sort(all(V));
V.resize(unique(all(V)) - V.begin());
}
int R, C;
vector<pii> Riv, P;
pii corner[] = {{0, 0}, {0, -1}, {-1, 0}, {-1, -1}};
bool Exist(pii X){
return X == *lower_bound(all(Riv), X);
}
vector<int> RE[N], CE[N];
vector<pii> Fen[N];
vector<int> PS[N];
void Add(pii P, int d){
//cerr << "# " << P.F << " " << P.S << " : " << d << '\n';
for(int idx = P.F; idx < N; idx += idx & (-idx))
Fen[idx].pb({P.S, d});
}
void init(int Ri, int Ci, int sr, int sc, int m, char *s){
R = Ri; C = Ci;
Riv.resize(m + 1);
Riv[0] = {sr, sc};
for(int i = 1; i <= m; i++){
if(s[i - 1] == 'N') sr --;
if(s[i - 1] == 'S') sr ++;
if(s[i - 1] == 'W') sc --;
if(s[i - 1] == 'E') sc ++;
Riv[i] = {sr, sc};
}
Unique(Riv);
for(auto &X : Riv)
for(auto &del : corner)
if(min(X.F + del.F, X.S + del.S) > 0)
P.pb({X.F + del.F, X.S + del.S});
Unique(P);
//for(auto X : Riv) cerr << X.F << ' ' << X.S << '\n';
Riv.pb({R + 2, C + 2});
for(auto &X : Riv){
if(X.F == R + 2) break;
if(!Exist({X.F, X.S - 1}))
RE[X.F].pb(X.S - 1);
if(!Exist({X.F, X.S + 1}))
RE[X.F].pb(X.S);
if(!Exist({X.F - 1, X.S}))
CE[X.S].pb(X.F - 1);
if(!Exist({X.F + 1, X.S}))
CE[X.S].pb(X.F);
}
int cnt;
for(auto X : P){
cnt = 0;
for(auto &del : corner)
if(Exist({X.F - del.F, X.S - del.S}))
cnt ++;
if(cnt & 1)
Add(X, cnt == 1 ? -1 : 1);
}
for(int i = 1; i < N; i++){
sort(all(Fen[i]));
PS[i].resize(Fen[i].size() + 1, 0);
for(int j = 1; j < (int) Fen[i].size(); j++){
PS[i][j] = PS[i][j - 1] + Fen[i][j - 1].S;
}
}
}
int Get(int x, int y){
int res = 0;
for(; x; x -= x & (-x)){
res += PS[x][upper_bound(all(Fen[x]), pii(y, 2)) - Fen[x].begin()];
}
return res;
}
int colour(int ar, int ac, int br, int bc){
int sum = 0;
if(!Exist({ar, ac})) sum ++;
if(!Exist({ar, bc})) sum ++;
if(!Exist({br, ac})) sum ++;
if(!Exist({br, bc})) sum ++;
if(ar < br && ac < bc){
sum += Get(br - 1, bc - 1);
sum -= Get(ar - 1, bc - 1);
sum -= Get(br - 1, ac - 1);
sum += Get(ar - 1, ac - 1);
}
sum += lower_bound(all(RE[ar]), bc) - upper_bound(all(RE[ar]), ac - 1);
sum += lower_bound(all(RE[br]), bc) - upper_bound(all(RE[br]), ac - 1);
sum += lower_bound(all(CE[ac]), br) - upper_bound(all(CE[ac]), ar - 1);
sum += lower_bound(all(CE[bc]), br) - upper_bound(all(CE[bc]), ar - 1);
//cerr << "! " << sum << '\n';
//assert(sum % 4 == 0);
return sum / 4;
}
#ifdef safar
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
init(6, 4, 3, 3, 9, "NWESSWEWS");
//cerr << Get(3, 2) << '\n';
cout << colour(2, 3, 2, 3) << '\n';
cout << colour(3, 2, 4, 4) << '\n';
cout << colour(5, 3, 6, 4) << '\n';
cout << colour(1, 2, 5, 3) << '\n';
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
25344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
25376 KB |
Output is correct |
| 2 |
Correct |
25 ms |
25344 KB |
Output is correct |
| 3 |
Incorrect |
204 ms |
32528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
25344 KB |
Output is correct |
| 2 |
Correct |
133 ms |
32576 KB |
Output is correct |
| 3 |
Correct |
119 ms |
32460 KB |
Output is correct |
| 4 |
Incorrect |
207 ms |
56908 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
25344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
25344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
