답안 #52343 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52343	2018-06-25T13:25:33 Z	imeimi2000	무지개나라 (APIO17_rainbow)	C++17	100 / 100	1132 ms	464800 KB

rainbow

#include "rainbow.h"
#include <algorithm>

using namespace std;

int r, c, m;
struct node {
    node *l, *r;
    int x;
    node() : l(0), r(0), x(0) {}
} ns[100001][20], xs[200002][20], ys[200002][20], vs[200004][20];

node n0;
node * _rt[100002], * _xt[200003], * _yt[200003], * _vt[200005];
node * rt[200001], * xt[200002], * yt[200002], * vt[200002];

void update(node * p, node * q, int s, int e, int x) {
    if (s == e) {
        q->x = p->x + 1;
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) {
        q->l = q + 1;
        q->r = p->r;
        update(p->l, q->l, s, m, x);
    }
    else {
        q->l = p->l;
        q->r = q + 1;
        update(p->r, q->r, m + 1, e, x);
    }
    q->x = q->l->x + q->r->x;
}

int query(node * p, node * q, int s, int e, int x, int y) {
    if (e < x || y < s) return 0;
    if (x <= s && e <= y) return q->x - p->x;
    int m = (s + e) / 2;
    return query(p->l, q->l, s, m, x, y) + query(p->r, q->r, m + 1, e, x, y);
}

struct point {
    int x, y;
    point move(char c) const {
        if (c == 'N') return { x - 1, y };
        if (c == 'S') return { x + 1, y };
        if (c == 'W') return { x, y - 1 };
        return { x, y + 1 };
    }
    bool operator<(const point &p) const {
        if (x == p.x) return y < p.y;
        return x < p.x;
    }
    bool operator==(const point &p) const {
        return x == p.x && y == p.y;
    }
} ps[100001], px[200002], py[200002], pv[400004];

int mnx, mny, mxx, mxy;
void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R;
    c = C;
    m = M;
    
    rt[0] = xt[0] = yt[0] = vt[0] = &n0;
    _rt[0] = _xt[0] = _yt[0] = _vt[0] = &n0;
    n0.l = n0.r = &n0;
    
    ps[0] = { sr, sc };
    mnx = mxx = sr;
    mny = mxy = sc;
    for (int i = 0; i < m; ++i) {
        ps[i + 1] = ps[i].move(S[i]);
        mnx = min(mnx, ps[i + 1].x);
        mxx = max(mxx, ps[i + 1].x);
        mny = min(mny, ps[i + 1].y);
        mxy = max(mxy, ps[i + 1].y);
    }
    sort(ps, ps + (m + 1));
    m = unique(ps, ps + (m + 1)) - ps;
    for (int i = 0; i < m; ++i) {
        px[i << 1] = px[i << 1 | 1] = ps[i];
        --px[i << 1].x;
        py[i << 1] = py[i << 1 | 1] = ps[i];
        --py[i << 1].y;
        pv[i << 2] = pv[i << 2 | 1] = pv[i << 2 | 2] = pv[i << 2 | 3] = ps[i];
        --pv[i << 2].x;
        --pv[i << 2].y;
        --pv[i << 2 | 1].x;
        --pv[i << 2 | 2].y;
    }
    sort(px, px + (m << 1));
    int nx = unique(px, px + (m << 1)) - px;
    sort(py, py + (m << 1));
    int ny = unique(py, py + (m << 1)) - py;
    sort(pv, pv + (m << 2));
    int nv = unique(pv, pv + (m << 2)) - pv;
    for (int i = 0, ip = 0, ix = 0, iy = 0, iv = 0; i <= 200000; ++i) {
        while (ip < m && ps[ip].x == i) {
            update(_rt[ip], _rt[ip + 1] = ns[ip], 0, c, ps[ip].y);
            ++ip;
        }
        rt[i] = _rt[ip];
        while (ix < nx && px[ix].x == i) {
            update(_xt[ix], _xt[ix + 1] = xs[ix], 0, c, px[ix].y);
            ++ix;
        }
        xt[i + 1] = _xt[ix];
        while (iy < ny && py[iy].x == i) {
            update(_yt[iy], _yt[iy + 1] = ys[iy], 0, c, py[iy].y);
            ++iy;
        }
        yt[i + 1] = _yt[iy];
        while (iv < nv && pv[iv].x == i) {
            update(_vt[iv], _vt[iv + 1] = vs[iv], 0, c, pv[iv].y);
            ++iv;
        }
        vt[i + 1] = _vt[iv];
    }
}

int colour(int ar, int ac, int br, int bc) {
    int ret = 1;
    if (ar < mnx && mxx < br && ac < mny && mxy < bc) ret = 2;
    
    int ct = br + bc - ar - ac + 2;
    ct <<= 1;
    int v = ct;
    v += query(vt[ar], vt[br], 0, c, ac, bc - 1);
    
    int e = ct;
    e += query(xt[ar], xt[br], 0, c, ac, bc);
    e += query(yt[ar], yt[br + 1], 0, c, ac, bc - 1);
    
    int pf = query(rt[ar - 1], rt[br], 0, c, ac, bc);
    
    ret -= v;
    ret += e;
    ret -= pf;
    
    return ret;
}

Subtask #1
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	232 ms	335352 KB	Output is correct
2	Correct	242 ms	335716 KB	Output is correct
3	Correct	232 ms	335716 KB	Output is correct
4	Correct	236 ms	335716 KB	Output is correct
5	Correct	259 ms	335912 KB	Output is correct
6	Correct	240 ms	335912 KB	Output is correct
7	Correct	229 ms	335912 KB	Output is correct
8	Correct	247 ms	335912 KB	Output is correct
9	Correct	256 ms	335912 KB	Output is correct
10	Correct	253 ms	335912 KB	Output is correct
11	Correct	236 ms	335912 KB	Output is correct
12	Correct	233 ms	336124 KB	Output is correct
13	Correct	238 ms	336160 KB	Output is correct
14	Correct	236 ms	336304 KB	Output is correct
15	Correct	232 ms	336304 KB	Output is correct
16	Correct	233 ms	336304 KB	Output is correct
17	Correct	237 ms	336304 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	336304 KB	Output is correct
2	Correct	237 ms	336304 KB	Output is correct
3	Correct	711 ms	343804 KB	Output is correct
4	Correct	872 ms	351484 KB	Output is correct
5	Correct	871 ms	354236 KB	Output is correct
6	Correct	723 ms	355148 KB	Output is correct
7	Correct	860 ms	357356 KB	Output is correct
8	Correct	453 ms	357356 KB	Output is correct
9	Correct	870 ms	365952 KB	Output is correct
10	Correct	912 ms	368664 KB	Output is correct
11	Correct	770 ms	369524 KB	Output is correct
12	Correct	549 ms	373676 KB	Output is correct
13	Correct	601 ms	377228 KB	Output is correct
14	Correct	561 ms	379996 KB	Output is correct
15	Correct	540 ms	380820 KB	Output is correct
16	Correct	727 ms	382356 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	232 ms	336304 KB	Output is correct
2	Correct	417 ms	385152 KB	Output is correct
3	Correct	360 ms	385152 KB	Output is correct
4	Correct	385 ms	385336 KB	Output is correct
5	Correct	350 ms	385336 KB	Output is correct
6	Correct	268 ms	385336 KB	Output is correct
7	Correct	309 ms	385336 KB	Output is correct
8	Correct	442 ms	385336 KB	Output is correct
9	Correct	405 ms	385336 KB	Output is correct
10	Correct	266 ms	385336 KB	Output is correct
11	Correct	325 ms	385336 KB	Output is correct
12	Correct	414 ms	385992 KB	Output is correct
13	Correct	385 ms	386188 KB	Output is correct
14	Correct	364 ms	386188 KB	Output is correct
15	Correct	343 ms	386188 KB	Output is correct
16	Correct	268 ms	386188 KB	Output is correct
17	Correct	307 ms	386188 KB	Output is correct
18	Correct	404 ms	386628 KB	Output is correct
19	Correct	390 ms	386684 KB	Output is correct
20	Correct	388 ms	386780 KB	Output is correct
21	Correct	415 ms	386780 KB	Output is correct
22	Correct	407 ms	386780 KB	Output is correct
23	Correct	263 ms	386780 KB	Output is correct
24	Correct	330 ms	386780 KB	Output is correct
25	Correct	418 ms	387412 KB	Output is correct
26	Correct	367 ms	387412 KB	Output is correct
27	Correct	390 ms	387512 KB	Output is correct
28	Correct	356 ms	387512 KB	Output is correct
29	Correct	278 ms	387512 KB	Output is correct
30	Correct	309 ms	387512 KB	Output is correct
31	Correct	408 ms	387796 KB	Output is correct
32	Correct	401 ms	388192 KB	Output is correct
33	Correct	388 ms	388192 KB	Output is correct

Subtask #4
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	232 ms	335352 KB	Output is correct
2	Correct	242 ms	335716 KB	Output is correct
3	Correct	232 ms	335716 KB	Output is correct
4	Correct	236 ms	335716 KB	Output is correct
5	Correct	259 ms	335912 KB	Output is correct
6	Correct	240 ms	335912 KB	Output is correct
7	Correct	229 ms	335912 KB	Output is correct
8	Correct	247 ms	335912 KB	Output is correct
9	Correct	256 ms	335912 KB	Output is correct
10	Correct	253 ms	335912 KB	Output is correct
11	Correct	236 ms	335912 KB	Output is correct
12	Correct	233 ms	336124 KB	Output is correct
13	Correct	238 ms	336160 KB	Output is correct
14	Correct	236 ms	336304 KB	Output is correct
15	Correct	232 ms	336304 KB	Output is correct
16	Correct	233 ms	336304 KB	Output is correct
17	Correct	237 ms	336304 KB	Output is correct
18	Correct	786 ms	388192 KB	Output is correct
19	Correct	429 ms	388192 KB	Output is correct
20	Correct	360 ms	388192 KB	Output is correct
21	Correct	379 ms	388192 KB	Output is correct
22	Correct	391 ms	390980 KB	Output is correct
23	Correct	421 ms	393844 KB	Output is correct
24	Correct	408 ms	396324 KB	Output is correct
25	Correct	392 ms	399216 KB	Output is correct
26	Correct	398 ms	402044 KB	Output is correct
27	Correct	531 ms	410548 KB	Output is correct
28	Correct	468 ms	410860 KB	Output is correct
29	Correct	548 ms	415916 KB	Output is correct
30	Correct	707 ms	424912 KB	Output is correct
31	Correct	236 ms	424912 KB	Output is correct
32	Correct	754 ms	424912 KB	Output is correct

Subtask #5
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	232 ms	335352 KB	Output is correct
2	Correct	242 ms	335716 KB	Output is correct
3	Correct	232 ms	335716 KB	Output is correct
4	Correct	236 ms	335716 KB	Output is correct
5	Correct	259 ms	335912 KB	Output is correct
6	Correct	240 ms	335912 KB	Output is correct
7	Correct	229 ms	335912 KB	Output is correct
8	Correct	247 ms	335912 KB	Output is correct
9	Correct	256 ms	335912 KB	Output is correct
10	Correct	253 ms	335912 KB	Output is correct
11	Correct	236 ms	335912 KB	Output is correct
12	Correct	233 ms	336124 KB	Output is correct
13	Correct	238 ms	336160 KB	Output is correct
14	Correct	236 ms	336304 KB	Output is correct
15	Correct	232 ms	336304 KB	Output is correct
16	Correct	233 ms	336304 KB	Output is correct
17	Correct	237 ms	336304 KB	Output is correct
18	Correct	786 ms	388192 KB	Output is correct
19	Correct	429 ms	388192 KB	Output is correct
20	Correct	360 ms	388192 KB	Output is correct
21	Correct	379 ms	388192 KB	Output is correct
22	Correct	391 ms	390980 KB	Output is correct
23	Correct	421 ms	393844 KB	Output is correct
24	Correct	408 ms	396324 KB	Output is correct
25	Correct	392 ms	399216 KB	Output is correct
26	Correct	398 ms	402044 KB	Output is correct
27	Correct	531 ms	410548 KB	Output is correct
28	Correct	468 ms	410860 KB	Output is correct
29	Correct	548 ms	415916 KB	Output is correct
30	Correct	707 ms	424912 KB	Output is correct
31	Correct	236 ms	424912 KB	Output is correct
32	Correct	754 ms	424912 KB	Output is correct
33	Correct	417 ms	385152 KB	Output is correct
34	Correct	360 ms	385152 KB	Output is correct
35	Correct	385 ms	385336 KB	Output is correct
36	Correct	350 ms	385336 KB	Output is correct
37	Correct	268 ms	385336 KB	Output is correct
38	Correct	309 ms	385336 KB	Output is correct
39	Correct	442 ms	385336 KB	Output is correct
40	Correct	405 ms	385336 KB	Output is correct
41	Correct	266 ms	385336 KB	Output is correct
42	Correct	325 ms	385336 KB	Output is correct
43	Correct	414 ms	385992 KB	Output is correct
44	Correct	385 ms	386188 KB	Output is correct
45	Correct	364 ms	386188 KB	Output is correct
46	Correct	343 ms	386188 KB	Output is correct
47	Correct	268 ms	386188 KB	Output is correct
48	Correct	307 ms	386188 KB	Output is correct
49	Correct	404 ms	386628 KB	Output is correct
50	Correct	390 ms	386684 KB	Output is correct
51	Correct	388 ms	386780 KB	Output is correct
52	Correct	415 ms	386780 KB	Output is correct
53	Correct	407 ms	386780 KB	Output is correct
54	Correct	263 ms	386780 KB	Output is correct
55	Correct	330 ms	386780 KB	Output is correct
56	Correct	418 ms	387412 KB	Output is correct
57	Correct	367 ms	387412 KB	Output is correct
58	Correct	390 ms	387512 KB	Output is correct
59	Correct	356 ms	387512 KB	Output is correct
60	Correct	278 ms	387512 KB	Output is correct
61	Correct	309 ms	387512 KB	Output is correct
62	Correct	408 ms	387796 KB	Output is correct
63	Correct	401 ms	388192 KB	Output is correct
64	Correct	388 ms	388192 KB	Output is correct
65	Correct	1132 ms	429556 KB	Output is correct
66	Correct	1069 ms	431408 KB	Output is correct
67	Correct	554 ms	431408 KB	Output is correct
68	Correct	647 ms	433692 KB	Output is correct
69	Correct	862 ms	442196 KB	Output is correct
70	Correct	675 ms	445028 KB	Output is correct
71	Correct	719 ms	447892 KB	Output is correct
72	Correct	671 ms	447928 KB	Output is correct
73	Correct	545 ms	447928 KB	Output is correct
74	Correct	574 ms	450480 KB	Output is correct
75	Correct	678 ms	459496 KB	Output is correct
76	Correct	836 ms	462244 KB	Output is correct
77	Correct	766 ms	464800 KB	Output is correct
78	Correct	711 ms	343804 KB	Output is correct
79	Correct	872 ms	351484 KB	Output is correct
80	Correct	871 ms	354236 KB	Output is correct
81	Correct	723 ms	355148 KB	Output is correct
82	Correct	860 ms	357356 KB	Output is correct
83	Correct	453 ms	357356 KB	Output is correct
84	Correct	870 ms	365952 KB	Output is correct
85	Correct	912 ms	368664 KB	Output is correct
86	Correct	770 ms	369524 KB	Output is correct
87	Correct	549 ms	373676 KB	Output is correct
88	Correct	601 ms	377228 KB	Output is correct
89	Correct	561 ms	379996 KB	Output is correct
90	Correct	540 ms	380820 KB	Output is correct
91	Correct	727 ms	382356 KB	Output is correct

답안 #52343

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 12.0 / 12.0

Subtask #3 24.0 / 24.0

Subtask #4 27.0 / 27.0

Subtask #5 26.0 / 26.0

Subtask #1
11.0 / 11.0

Subtask #2
12.0 / 12.0

Subtask #3
24.0 / 24.0

Subtask #4
27.0 / 27.0

Subtask #5
26.0 / 26.0