oj.uz

Submission #201397

# Submission time Handle Problem Language Result Execution time Memory
201397 2020-02-10T11:19:16 Z dimash241 Land of the Rainbow Gold (APIO17_rainbow) C++17
50 / 100
 1162 ms 59844 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;
const int MAXN = 1e5 + 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 rx, int ly, int ry) {
    	int res = 0;
    	while (rx >= 0) {
    		res += upper_bound(every(t[rx]), ry) 
    			- lower_bound(every(t[rx]), ly);
    		rx = (rx & (rx + 1)) - 1;
    	}
 
    	return res;
    }
 
    int get (int lx, int rx, int ly, int ry) {
    	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;
	{
    	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 < 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 */

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9852 KB Output is correct
2 Correct 16 ms 10232 KB Output is correct
3 Correct 14 ms 9848 KB Output is correct
4 Correct 14 ms 9848 KB Output is correct
5 Correct 16 ms 10360 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Correct 11 ms 9720 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 11 ms 9720 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 14 ms 9976 KB Output is correct
12 Correct 15 ms 10104 KB Output is correct
13 Correct 17 ms 10488 KB Output is correct
14 Correct 17 ms 10744 KB Output is correct
15 Correct 11 ms 9720 KB Output is correct
16 Correct 11 ms 9720 KB Output is correct
17 Correct 10 ms 9720 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 10 ms 9720 KB Output is correct
3 Correct 210 ms 37972 KB Output is correct
4 Correct 301 ms 58692 KB Output is correct
5 Correct 288 ms 58288 KB Output is correct
6 Correct 249 ms 46660 KB Output is correct
7 Correct 276 ms 46072 KB Output is correct
8 Correct 130 ms 18376 KB Output is correct
9 Correct 296 ms 59716 KB Output is correct
10 Correct 291 ms 59460 KB Output is correct
11 Correct 258 ms 46536 KB Output is correct
12 Correct 170 ms 57284 KB Output is correct
13 Correct 170 ms 59844 KB Output is correct
14 Correct 177 ms 59592 KB Output is correct
15 Correct 172 ms 46020 KB Output is correct
16 Correct 225 ms 42940 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9852 KB Output is correct
2 Correct 16 ms 10232 KB Output is correct
3 Correct 14 ms 9848 KB Output is correct
4 Correct 14 ms 9848 KB Output is correct
5 Correct 16 ms 10360 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Correct 11 ms 9720 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 11 ms 9720 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 14 ms 9976 KB Output is correct
12 Correct 15 ms 10104 KB Output is correct
13 Correct 17 ms 10488 KB Output is correct
14 Correct 17 ms 10744 KB Output is correct
15 Correct 11 ms 9720 KB Output is correct
16 Correct 11 ms 9720 KB Output is correct
17 Correct 10 ms 9720 KB Output is correct
18 Correct 1162 ms 34784 KB Output is correct
19 Correct 308 ms 11900 KB Output is correct
20 Correct 238 ms 10624 KB Output is correct
21 Correct 263 ms 10872 KB Output is correct
22 Correct 297 ms 11132 KB Output is correct
23 Correct 283 ms 11788 KB Output is correct
24 Correct 279 ms 11000 KB Output is correct
25 Correct 317 ms 11256 KB Output is correct
26 Correct 313 ms 11460 KB Output is correct
27 Correct 417 ms 31612 KB Output is correct
28 Correct 389 ms 24136 KB Output is correct
29 Correct 378 ms 28996 KB Output is correct
30 Correct 864 ms 55236 KB Output is correct
31 Correct 14 ms 9720 KB Output is correct
32 Correct 737 ms 33476 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9852 KB Output is correct
2 Correct 16 ms 10232 KB Output is correct
3 Correct 14 ms 9848 KB Output is correct
4 Correct 14 ms 9848 KB Output is correct
5 Correct 16 ms 10360 KB Output is correct
6 Correct 10 ms 9720 KB Output is correct
7 Correct 11 ms 9720 KB Output is correct
8 Correct 11 ms 9720 KB Output is correct
9 Correct 11 ms 9720 KB Output is correct
10 Correct 11 ms 9720 KB Output is correct
11 Correct 14 ms 9976 KB Output is correct
12 Correct 15 ms 10104 KB Output is correct
13 Correct 17 ms 10488 KB Output is correct
14 Correct 17 ms 10744 KB Output is correct
15 Correct 11 ms 9720 KB Output is correct
16 Correct 11 ms 9720 KB Output is correct
17 Correct 10 ms 9720 KB Output is correct
18 Correct 1162 ms 34784 KB Output is correct
19 Correct 308 ms 11900 KB Output is correct
20 Correct 238 ms 10624 KB Output is correct
21 Correct 263 ms 10872 KB Output is correct
22 Correct 297 ms 11132 KB Output is correct
23 Correct 283 ms 11788 KB Output is correct
24 Correct 279 ms 11000 KB Output is correct
25 Correct 317 ms 11256 KB Output is correct
26 Correct 313 ms 11460 KB Output is correct
27 Correct 417 ms 31612 KB Output is correct
28 Correct 389 ms 24136 KB Output is correct
29 Correct 378 ms 28996 KB Output is correct
30 Correct 864 ms 55236 KB Output is correct
31 Correct 14 ms 9720 KB Output is correct
32 Correct 737 ms 33476 KB Output is correct
33 Runtime error 90 ms 47684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Halted 0 ms 0 KB -