oj.uz

Submission #200371

# Submission time Handle Problem Language Result Execution time Memory
200371 2020-02-06T12:17:09 Z dimash241 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 133 ms 26088 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, 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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5880 KB Output is correct
2 Correct 24 ms 5880 KB Output is correct
3 Correct 48 ms 6008 KB Output is correct
4 Correct 48 ms 6008 KB Output is correct
5 Correct 23 ms 6008 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 9 ms 5752 KB Output is correct
8 Correct 8 ms 5752 KB Output is correct
9 Correct 8 ms 5752 KB Output is correct
10 Correct 9 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 32 ms 6008 KB Output is correct
14 Correct 24 ms 6008 KB Output is correct
15 Correct 8 ms 5756 KB Output is correct
16 Correct 9 ms 5752 KB Output is correct
17 Correct 9 ms 5752 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5752 KB Output is correct
2 Correct 9 ms 5752 KB Output is correct
3 Correct 114 ms 23060 KB Output is correct
4 Correct 127 ms 23996 KB Output is correct
5 Correct 133 ms 24124 KB Output is correct
6 Correct 132 ms 24252 KB Output is correct
7 Incorrect 130 ms 24468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5756 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 24 ms 5880 KB Output is correct
3 Correct 48 ms 6008 KB Output is correct
4 Correct 48 ms 6008 KB Output is correct
5 Correct 23 ms 6008 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 9 ms 5752 KB Output is correct
8 Correct 8 ms 5752 KB Output is correct
9 Correct 8 ms 5752 KB Output is correct
10 Correct 9 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 32 ms 6008 KB Output is correct
14 Correct 24 ms 6008 KB Output is correct
15 Correct 8 ms 5756 KB Output is correct
16 Correct 9 ms 5752 KB Output is correct
17 Correct 9 ms 5752 KB Output is correct
18 Runtime error 50 ms 26088 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 24 ms 5880 KB Output is correct
3 Correct 48 ms 6008 KB Output is correct
4 Correct 48 ms 6008 KB Output is correct
5 Correct 23 ms 6008 KB Output is correct
6 Correct 8 ms 5752 KB Output is correct
7 Correct 9 ms 5752 KB Output is correct
8 Correct 8 ms 5752 KB Output is correct
9 Correct 8 ms 5752 KB Output is correct
10 Correct 9 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 32 ms 6008 KB Output is correct
14 Correct 24 ms 6008 KB Output is correct
15 Correct 8 ms 5756 KB Output is correct
16 Correct 9 ms 5752 KB Output is correct
17 Correct 9 ms 5752 KB Output is correct
18 Runtime error 50 ms 26088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -