Submission #1340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340		kentsfield	개구리 (KOI13_frog)	C++98	0 / 22	29 ms	75860 KiB

frog

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
 
struct ii {
    int x, y, z;
    ii(int x, int y, int z): x(x), y(y), z(z) {}
    ii(){}
};
 
bool tree[15000001], sf;
int D, N, R, cnt[15000001];
ii p[100001];
vector < vector <int> > v;
 
inline bool cmp(const ii& a, const ii& b) {
    return sf ? a.y < b.y : a.x < b.x;
}
 
void Up(int x, int L, int R, int nL, int nR, int v)
{
    if (nL <= L && R <= nR) {
        cnt[x] += v;
    }
 
    else {
        int m = (nL + nR) >> 1;
        if (L <= m) Up(x * 2, L, R, nL, m, v);
        if (m < R) Up(x * 2 + 1, L, R, m + 1, R, v);
    }
 
    tree[x] = 0;
 
    if (cnt[x]) {
        tree[x] = 1;
    }
 
    else if (!cnt[x] && nL < nR) {
        tree[x] = tree[x * 2 + 1] | tree[x * 2];
    }
}
 
bool Read(int x, int L, int R, int nL, int nR)
{
    bool ret = 0;
 
    if (nL <= L && R <= nR) {
        return tree[x];
    }
 
    else {
        int m = (nL + nR) >> 1;
        if (L <= m) ret |= Read(x * 2, L, R, nL, m);
        if (m < R) ret |= Read(x * 2 + 1, L, R, m + 1, nR);
    }
 
    return ret;
}
 
int main()
{
    scanf("%d%d", &N, &R);
 
    v.resize(N + 1);
 
    for (int i = 0; i < N; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
        p[i].z = i + 1;
    }
 
    scanf("%d", &D);
 
    sort(p, p + N, cmp);
 
    for (int i = 0; i < N; i++) {
 
        if (i > 0 && p[i].x - p[i - 1].x >= D &&
            Read(1, p[i].y, p[i].y + R, 0, 10000000)) {
            v[p[i - 1].z].push_back(p[i].z);
            v[p[i].z].push_back(p[i - 1].z);
        }
 
        if (i > 0) {
            Up(1, p[i - 1].y, p[i - 1].y + R, 0, 10000000, -1);
        }
 
        Up(1, p[i].y, p[i].y + R, 0, 10000000, 1);
    }
 
    sf = 1;
    sort(p, p + N, cmp);
    memset(tree, 0, sizeof tree);
    memset(cnt, 0, sizeof cnt);
 
 
    for (int i = 0; i < N; i++) {
 
        if (i > 0 && p[i].y - p[i - 1].y >= D &&
            Read(1, p[i].x, p[i].x + R, 0, 10000000)) {
            v[p[i - 1].z].push_back(p[i].z);
            v[p[i].z].push_back(p[i - 1].z);
        }
 
        if (i > 0) {
            Up(1, p[i - 1].x, p[i - 1].x + R, 0, 10000000, -1);
        }
 
        Up(1, p[i].x, p[i].x + R, 0, 10000000, 1);
    }
 
    queue <int> q;
    bool vis[100001] = {};
 
    for (int i = 0; i < N; i++) {
        if (p[i].x <= 0 && 0 <= p[i].x + R &&
            p[i].y <= 0 && 0 <= p[i].y + R) {
            q.push(p[i].z);
            vis[p[i].z] = 1;
        }
    }
 
    int ans = 0;
 
    while (!q.empty()) {
        int w = q.front(); q.pop();
        ans = max(ans, p[w].x + p[w].y + R * 2);
 
        for (int i = 0; i < v[w].size(); i++) {
            if (!vis[v[w][i]]) {
                vis[v[w][i]] = 1;
                q.push(v[w][i]);
            }
        }
 
    }
 
    printf("%d\n", ans);
    return 0;
}

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