제출 #528052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528052		qwerasdfzxcl	식물 비교 (IOI20_plants)	C++14	100 / 100	1016 ms	58868 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e9;
int n, a[200200], idxa[200200];
struct Seg2{
    pair<int, int> tree[800800];
    int lazy[800800];
    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r) {tree[i] = {INF, l}; return;}

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        tree[i].first += lazy[i];
        if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void update2(int i, int l, int r, int s, int x){
        propagate(i, l, r);
        if (r<s || s<l) return;
        if (l==r) {tree[i].second = x; return;}
        int m = (l+r)>>1;
        update2(i<<1, l, m, s, x); update2(i<<1|1, m+1, r, s, x);
        tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void update(int l, int r, int x){
        if (r<=n) update(1, 1, n, l, r, x);
        else{
            update(1, 1, n, l, n, x);
            update(1, 1, n, 1, r-n, x);
        }
    }
}tree2;
struct Seg1{
    int tree[800800], lazy[800800];
    void init(int i, int l, int r, vector<int> &vec){
        lazy[i] = 0;
        if (l==r) {tree[i] = vec[l-1]; return;}

        int m = (l+r)>>1;
        init(i<<1, l, m, vec); init(i<<1|1, m+1, r, vec);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void find(int i, int l, int r, int x){
        propagate(i, l, r);
        if (tree[i]<x) return;
        if (l==r){
            assert(tree[i]==x);
            //printf("YES: %d\n", l);
            tree2.update(l, l, -INF);
            tree2.update(l+1, l+x, 1);

            update(1, 1, n, l, l, -INF);
            return;
        }

        int m = (l+r)>>1;
        find(i<<1, l, m, x); find(i<<1|1, m+1, r, x);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void update(int s, int e, int x){
        if (s>0) update(1, 1, n, s, e, x);
        else{
            update(1, 1, n, s+n, n, x);
            update(1, 1, n, 1, e, x);
        }
    }
}tree1;

struct Seg3{
    pair<int, int> tree[400400];
    int sz;
    void init(int n, int *a){
        sz = n+1;
        for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz};
        for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
    void update(int p, int x){
        for (tree[p+=sz].first=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    pair<int, int> query(int l, int r){
        pair<int, int> ret = {INF, -1};
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
    int queryc(int l, int r){
        if (l<=0){
            auto p = min(query(l+n, sz), query(1, r+1));
            return p.second;
        }
        if (r>n){
            auto p = min(query(l, sz), query(1, r-n+1));
            return p.second;
        }
        return query(l, r+1).second;
    }
}tree3;

vector<int> r;
int k, adj[200200][2][20], nxt[200200][2];

void init(int K, vector<int> R) {
    k = K, r = R;
    n = r.size();
    tree1.init(1, 1, n, r);
    tree2.init(1, 1, n);
    tree2.update2(1, 1, n, 1, INF+1);

    for (int i=1;i<=n;i++){
        tree1.find(1, 1, n, k-1);
        assert(tree2.tree[1].first==0);
        a[i] = tree2.tree[1].second;
        if (a[i]>=INF) a[i] -= INF;
        //printf("a[%d] = %d\n", i, a[i]);

        tree2.update(a[i], a[i], INF);
        tree2.update(a[i]+1, a[i]+k-1, -1);
        tree1.update(a[i]-k+1, a[i]-1, 1);
    }

    for (int i=1;i<=n;i++) idxa[a[i]] = i;

    //printf("idxa: ");
    //for (int i=1;i<=n;i++) printf("%d ", idxa[i]);
    //printf("\n");

    tree3.init(n, idxa);
    for (int i=1;i<=n;i++){
        int pos = a[i];
        int l = tree3.queryc(pos-k+1, pos-1), r = tree3.queryc(pos+1, pos+k-1);
        adj[pos][0][0] = l, adj[pos][1][0] = r;
        nxt[pos][0] = nxt[pos][1] = -1;

        if (pos<l) adj[pos][0][0] = -1, nxt[pos][0] = l;
        if (pos>r) adj[pos][1][0] = -1, nxt[pos][1] = r;

        //printf("%d: %d %d %d %d\n", pos, adj[pos][0][0], adj[pos][1][0], nxt[pos][0], nxt[pos][1]);

        tree3.update(pos, INF+1);
    }

    for (int k=1;k<20;k++){
        for (int i=1;i<=n;i++){
            for (int j=0;j<2;j++){
                if (adj[i][j][k-1]==-1) {adj[i][j][k] = -1; continue;}
                adj[i][j][k] = adj[adj[i][j][k-1]][j][k-1];
            }
        }
    }
}

int dist(int x, int y){
    if (x<y) return y - x;
    return n + y - x;
}

bool is_reachable(int x, int y){
    int s = x;
    if (y<x){
        for (int t=19;t>=0;t--) if (adj[s][1][t]!=-1) s = adj[s][1][t];
        if (dist(s, y)<k && idxa[s] < idxa[y]) return 1;

        s = nxt[s][1];
    }
    if (s!=-1){
        for (int t=19;t>=0;t--) if (adj[s][1][t]!=-1 && adj[s][1][t] < y && dist(adj[s][1][t], y) >= k) s = adj[s][1][t];
        if (s!=-1 && dist(s, y) >= k) s = adj[s][1][0];
        if (s!=-1 && dist(s, y)<k && idxa[s] < idxa[y]) return 1;
    }

    s = x;
    if (x<y){
        for (int t=19;t>=0;t--) if (adj[s][0][t]!=-1) s = adj[s][0][t];
        if (dist(y, s)<k && idxa[s] < idxa[y]) return 1;

        s = nxt[s][0];
    }
    if (s!=-1){
        for (int t=19;t>=0;t--) if (adj[s][0][t]!=-1 && adj[s][0][t] > y && dist(y, adj[s][0][t]) >= k) s = adj[s][0][t];
        if (s!=-1 && dist(y, s) >= k) s = adj[s][0][0];
        if (s!=-1 && dist(y, s)<k && idxa[s] < idxa[y]) return 1;
    }

    return 0;
}

int compare_plants(int x, int y) {
    ++x, ++y;

    if (is_reachable(x, y)) return -1;
    if (is_reachable(y, x)) return 1;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25