oj.uz

Submission #200373

# Submission time Handle Problem Language Result Execution time Memory
200373 2020-02-06T12:36:48 Z dimash241 Land of the Rainbow Gold (APIO17_rainbow) C++17
23 / 100
 156 ms 26200 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 == 1) && (br == 1)) _use = &r1;
        else if ((ar == 1) && (br == 2)) _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, m)) - 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 25 ms 6008 KB Output is correct
3 Correct 56 ms 6008 KB Output is correct
4 Correct 51 ms 6008 KB Output is correct
5 Correct 27 ms 6008 KB Output is correct
6 Correct 8 ms 5880 KB Output is correct
7 Correct 9 ms 5880 KB Output is correct
8 Correct 8 ms 5880 KB Output is correct
9 Correct 9 ms 5880 KB Output is correct
10 Correct 8 ms 5752 KB Output is correct
11 Correct 44 ms 6008 KB Output is correct
12 Correct 41 ms 6008 KB Output is correct
13 Correct 28 ms 6008 KB Output is correct
14 Correct 24 ms 6008 KB Output is correct
15 Correct 9 ms 5752 KB Output is correct
16 Correct 9 ms 5752 KB Output is correct
17 Correct 9 ms 5756 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 9 ms 5756 KB Output is correct
3 Correct 120 ms 23060 KB Output is correct
4 Correct 134 ms 23484 KB Output is correct
5 Correct 140 ms 23608 KB Output is correct
6 Correct 131 ms 23612 KB Output is correct
7 Correct 156 ms 24112 KB Output is correct
8 Correct 118 ms 23968 KB Output is correct
9 Correct 144 ms 23996 KB Output is correct
10 Correct 139 ms 24244 KB Output is correct
11 Correct 146 ms 24256 KB Output is correct
12 Correct 108 ms 23900 KB Output is correct
13 Correct 111 ms 23992 KB Output is correct
14 Correct 129 ms 24252 KB Output is correct
15 Correct 122 ms 24252 KB Output is correct
16 Correct 112 ms 23644 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Runtime error 32 ms 21372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 25 ms 6008 KB Output is correct
3 Correct 56 ms 6008 KB Output is correct
4 Correct 51 ms 6008 KB Output is correct
5 Correct 27 ms 6008 KB Output is correct
6 Correct 8 ms 5880 KB Output is correct
7 Correct 9 ms 5880 KB Output is correct
8 Correct 8 ms 5880 KB Output is correct
9 Correct 9 ms 5880 KB Output is correct
10 Correct 8 ms 5752 KB Output is correct
11 Correct 44 ms 6008 KB Output is correct
12 Correct 41 ms 6008 KB Output is correct
13 Correct 28 ms 6008 KB Output is correct
14 Correct 24 ms 6008 KB Output is correct
15 Correct 9 ms 5752 KB Output is correct
16 Correct 9 ms 5752 KB Output is correct
17 Correct 9 ms 5756 KB Output is correct
18 Runtime error 60 ms 26200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 25 ms 6008 KB Output is correct
3 Correct 56 ms 6008 KB Output is correct
4 Correct 51 ms 6008 KB Output is correct
5 Correct 27 ms 6008 KB Output is correct
6 Correct 8 ms 5880 KB Output is correct
7 Correct 9 ms 5880 KB Output is correct
8 Correct 8 ms 5880 KB Output is correct
9 Correct 9 ms 5880 KB Output is correct
10 Correct 8 ms 5752 KB Output is correct
11 Correct 44 ms 6008 KB Output is correct
12 Correct 41 ms 6008 KB Output is correct
13 Correct 28 ms 6008 KB Output is correct
14 Correct 24 ms 6008 KB Output is correct
15 Correct 9 ms 5752 KB Output is correct
16 Correct 9 ms 5752 KB Output is correct
17 Correct 9 ms 5756 KB Output is correct
18 Runtime error 60 ms 26200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -