oj.uz

답안 #200370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200370 2020-02-06T12:14:41 Z dimash241 무지개나라 (APIO17_rainbow) C++17
0 / 100
 51 ms 21368 KB 
//#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;
int u[55][55];
const int MAXN = 1e5 + 5;
unordered_map < int, int > d[MAXN];
int timer;

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 !d[x][y];
}
vector < pair < int, int > > r1, r2, r12, p;

void init(int _n, int _m, int x, int y, int _k, char *s) {
	n = _n, m = _m, k = _k;
	d[x][y] = 1;
	for (int i = 0; i < k; ++i) {
		moveto(x, y, s[i]);
	//	printf("row column : %d %d\n", x, y);
		d[x][y] = 1;
		p.pb(mp(x, y));
	}

	sort(every(p));
	p.resize(unique(every(p)) - p.begin());

	if (n <= 2) {
		int lst = 0;
		for (int i = 1; i <= m; ++i) {
			if(d[1][i]) {
				if (lst != (i - 1)) r1.pb(mp(lst + 1, i - 1));
				lst = i;
			}
		}
		if (lst != m) r1.pb(mp(lst + 1, m));

		lst = 0;
		for (int i = 1; i <= m; ++i) {
			if(d[2][i]) {
				if (lst != (i - 1)) r2.pb(mp(lst + 1, i - 1));
				lst = i;
			}
		}
		if (lst != m) r2.pb(mp(lst + 1, m));

		lst = 0;
		for (int i = 1; i <= m; ++i) {
			if(d[2][i] && d[1][i]) {
				if (lst != (i - 1)) r12.pb(mp(lst + 1, i - 1));
				lst = i;
			}
		}
		if (lst != m) r12.pb(mp(lst + 1, m));

	}
}

void dfs (int ax, int bx) {
	u[ax][bx] = timer;
//	cout << ax << ' ' << bx << '\n';
	for (int dir = 0; dir < 4; ++dir) {
		int ay = ax + dx[dir];
		int by = bx + dy[dir];
		
		if (cordi(ay, by) && u[ay][by] != timer)
			dfs(ay, by);
	}
} 

int colour(int ar, int ac, int br, int bc) {
	lx = ar;
	rx = br;
	ly = ac;
	ry = bc;
	if (n == 2) {
		vector < pair < int, int > > *_use;
        if ((ar == 0) && (br == 0)) _use = &r1;
        else if ((ar == 0) && (br == 1)) _use = &r12;
        else _use = &r2;
        vector < pair < int, int > > &use = *_use;
        int l = lower_bound(every(use), mp(ac, 0)) - use.begin() - 1;
        if ((l == -1) || (use[l].second < ac)) l++;
        int r = upper_bound(every(use), mp(bc, 3)) - use.begin() - 1;
        return r - l + 1;
	}
	++timer;
	int cnt = 0;
	for (int ax = ar; ax <= br; ++ax) {
		for (int bx = ac; bx <= bc; ++bx) {
			if (cordi(ax, bx) && u[ax][bx] != timer) {
				//cout << ax << ' ' << bx << '\n';
				dfs(ax, bx);
				++cnt;
			}
		}
	}
    return cnt;
}
/*

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 */

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 24 ms 5880 KB Output is correct
3 Correct 51 ms 6008 KB Output is correct
4 Correct 48 ms 6008 KB Output is correct
5 Correct 25 ms 6008 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 8 ms 5752 KB Output is correct
8 Correct 9 ms 5752 KB Output is correct
9 Correct 8 ms 5752 KB Output is correct
10 Correct 8 ms 5752 KB Output is correct
11 Correct 41 ms 6008 KB Output is correct
12 Correct 38 ms 6008 KB Output is correct
13 Correct 30 ms 5880 KB Output is correct
14 Correct 23 ms 6012 KB Output is correct
15 Correct 8 ms 5752 KB Output is correct
16 Incorrect 9 ms 6008 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5752 KB Output is correct
2 Runtime error 36 ms 21368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 24 ms 5880 KB Output is correct
3 Correct 51 ms 6008 KB Output is correct
4 Correct 48 ms 6008 KB Output is correct
5 Correct 25 ms 6008 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 8 ms 5752 KB Output is correct
8 Correct 9 ms 5752 KB Output is correct
9 Correct 8 ms 5752 KB Output is correct
10 Correct 8 ms 5752 KB Output is correct
11 Correct 41 ms 6008 KB Output is correct
12 Correct 38 ms 6008 KB Output is correct
13 Correct 30 ms 5880 KB Output is correct
14 Correct 23 ms 6012 KB Output is correct
15 Correct 8 ms 5752 KB Output is correct
16 Incorrect 9 ms 6008 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 24 ms 5880 KB Output is correct
3 Correct 51 ms 6008 KB Output is correct
4 Correct 48 ms 6008 KB Output is correct
5 Correct 25 ms 6008 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 8 ms 5752 KB Output is correct
8 Correct 9 ms 5752 KB Output is correct
9 Correct 8 ms 5752 KB Output is correct
10 Correct 8 ms 5752 KB Output is correct
11 Correct 41 ms 6008 KB Output is correct
12 Correct 38 ms 6008 KB Output is correct
13 Correct 30 ms 5880 KB Output is correct
14 Correct 23 ms 6012 KB Output is correct
15 Correct 8 ms 5752 KB Output is correct
16 Incorrect 9 ms 6008 KB Output isn't correct
17 Halted 0 ms 0 KB -