Submission #1428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1428		tncks0121	개구리 (KOI13_frog)	C++98	22 / 22	212 ms	16220 KiB

frog

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef long double llf;
typedef unsigned long long llu;
const int INF = 987654321;
const ll LINF = (ll)1e15;

const int N_ = 100005;
const int R_ = 10005;
const int LF = 131072*2;

namespace DisjointSet {
    int grp[N_];
    void init() { for(int i = 1; i < N_; i++) grp[i] = i; }
    int get(int x) {
        int r = x;
        while(r != grp[r]) r = grp[r];
        while(x != grp[x]) {
            int p = grp[x];
            grp[x] = r;
            x = p;
        }
        return r;
    }
    bool merge (int u, int v) {
        u = get(u); v = get(v);
        grp[u] = v;
        return (u != v);
    }
};

namespace SegTree {
    int Tree[LF+LF];

    void init() {
        memset(Tree, 0, sizeof Tree);
    }

    void update (int l, int r, int v) {
        l += LF; r += LF;
        while(l <= r) {
            if((l & 1) == 1) if(Tree[l] < v) Tree[l] = v;
            if((r & 1) == 0) if(Tree[r] < v) Tree[r] = v;
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }
    }

    int get (int x) {
        int ret = -1;
        for(x += LF; x > 0; x >>= 1) if(ret < Tree[x]) ret = Tree[x];
        return ret;
    }
};

struct P {
    int x, y, n;
    P (): x(0), y(0) { }
    P (int x, int y): x(x), y(y) { }
    P (int x, int y, int n): x(x), y(y), n(n) { }
    bool operator < (const P &t) const { return x != t.x ? x < t.x : y < t.y; }
};

int N, R, J;
P D[N_];

P A[N_*5]; int AN;
int *X[N_*5];

bool cmpX (int *a, int *b) {
    return *a < *b;
}

int bef[N_*5];

void connect () {
    int i, j;

    AN = 0;

    for(i = 1; i <= N; i++) {
        A[++AN] = P(D[i].x, D[i].y, i);
        A[++AN] = P(D[i].x, D[i].y+R, i);
        A[++AN] = P(D[i].x+R, D[i].y, -i);
        A[++AN] = P(D[i].x+R, D[i].y+R, -i);
    }

    sort(A+1, A+AN+1);

    for(i = 1; i <= AN; i++) X[i] = &A[i].y;
    sort(X+1, X+AN+1, cmpX);

    int last = *X[1]; *X[1] = 1;
    for(i = 2, j = 1; i <= AN; i++) {
        if(*X[i] != last) ++j;
        last = *X[i];
        *X[i] = j;
    }

    SegTree::init();
    for(i = 1; i <= AN; i++) {
        P &p = A[i];
        if(p.n > 0) {
            int w = SegTree::get(p.y);
            if(w > 0 && abs(p.x - A[w].x) <= J) DisjointSet::merge(abs(A[w].n), p.n);
        }else {
            if(!bef[p.n]) {
                bef[p.n] = p.y;
            }else {
                SegTree::update(bef[p.n], p.y, i);
                bef[p.n] = 0;
            }
        }
    }
}

int main() {
    int i, j;

    scanf("%d%d", &N, &R);
    for(i = 1; i <= N; i++) scanf("%d%d", &D[i].x, &D[i].y);
    scanf("%d", &J);

    DisjointSet::init();

    connect();
    for(i = 1; i <= N; i++) swap(D[i].x, D[i].y);
    connect();

    int f = -1;
    int res = 0;

    for(i = 1; i <= N; i++) {
        if(D[i].x == 0 && D[i].y == 0) f = DisjointSet::get(i);
    }

    for(i = 1; i <= N; i++) {
        if(DisjointSet::get(i) == f) {
            res = max(res, D[i].x + D[i].y + R + R);
        }
    }

    printf("%d\n", res);
    return 0;
}

• Subtask 1: 1.98 / 1.98
• Subtask 2: 2.64 / 2.64
• Subtask 3: 3.52 / 3.52
• Subtask 4: 4.18 / 4.18
• Subtask 5: 4.62 / 4.62
• Subtask 6: 5.06 / 5.06