| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 201381 | dimash241 | 무지개나라 (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//# include <x86intrin.h>
# include <bits/stdc++.h>
#include "rainbow.h"
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y) for (ll i = x; i <= y; i ++)
#define FOr(i,x,y) for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to... Red
inline void Input_Output () {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
}
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int n, m, k, q;
const int MAXN = 3e5 + 5;
inline void moveto (int &x, int &y, char c) {
if (c == 'N') x--;
if (c == 'S') x++;
if (c == 'W') y--;
if (c == 'E') y++;
assert(x > 0 && y > 0 && x <= n && y <= m);
}
int lx, ly, rx, ry;
bool cordi (int x, int y) {
if(!(x >= lx && y >= ly && x <= rx && y <= ry)) return 0;
return 1;
}
using pt = pair < int, int >;
vector < pt > vv[4];
struct BIT {
vector<int> t[MAXN + 5];
void upd (int x, int y) {
if (x < 1 || y < 1) {
return;
}
for (; x <= MAXN; x |= (x + 1)) {
t[x].pb(y);
}
}
int get (int x, int ly, int ry) {
ll ret = 0;
for (; x > 0; --x) {
res += upper_bound(every(t[x]), ry) - lower_bound(every(t[x]), ly);
x &= (x + 1);
}
return ret;
}
int get (int lx, int rx, int ly, int ry) {
if (lx > rx) return 0;
if (ly > ry) return 0;
return get(rx, ly, ry) - get(lx - 1, ly, ry);
}
} T[4];
void init(int _n, int _m, int x, int y, int _k, char *s) {
n = _n, m = _m, k = _k;
lx = rx = x;
ly = ry = y;
for (int i = 0; i < k; ++i) {
moveto(x, y, s[i]);
lx = min(lx, x);
rx = max(rx, x);
ly = min(ly, y);
ry = max(ry, y);
vv[0].pb(mp(x, y));
vv[1].pb(mp(x, y));
vv[1].pb(mp(x - 1, y));
vv[2].pb(mp(x, y));
vv[2].pb(mp(x, y - 1));
vv[3].pb(mp(x, y));
vv[3].pb(mp(x - 1, y));
vv[3].pb(mp(x, y - 1));
vv[3].pb(mp(x - 1, y - 1));
}
for (int i = 0; i < 4; ++i) {
sort(every(vv[i]), [&](pt a, pt b) { return mp(a.S, a.F) < mp(b.S, b.F); });
vv[i].resize(unique(every(vv[i])) - vv[i].begin());
for (auto it : vv[i]) {
T[i].upd(it.first, it.second);
}
}
}
int colour(int ax, int ay, int bx, int by) {
ll ans = 1;
if (ax < lx && rx < bx && ay < ly && ry < by) {
++ans;
}
ans += T[1].get(ax, bx - 1, ay, by);
ans += T[2].get(ax, bx, ay, by - 1);
ans -= T[3].get(ax, bx - 1, ay, by - 1);
ans -= T[0].get(ax, bx, ay, by);
return ans;
}
/*
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];
int main() {
scanf("%d %d %d %d", &R, &C, &M, &Q);
scanf("%d %d", &sr, &sc);
if (M > 0) {
scanf(" %s ", S);
}
init(R, C, sr, sc, M, S);
int query;
for (query = 0; query < Q; query++) {
int ar, ac, br, bc;
scanf("%d %d %d %d", &ar, &ac, &br, &bc);
printf("%d\n", colour(ar, ac, br, bc));
}
return 0;
}
// B...a */