Submission #300153

#	Time	Username	Problem	Language	Result	Execution time	Memory
300153		model_code	Comparing Plants (IOI20_plants)	Java	100 / 100	1224 ms	45472 KiB

plants

// plants-yanhao-ac

class segtree {
	final int n_bits=18;
	final int inf = (int)1e9;
	int[] arr = new int [1<<(n_bits+1)];
	int[] lazyadd = new int [1<<(n_bits+1)];
    int node = 1;
    int lazy = 0;
	int low(int i) {
		return (i<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits);
	}
	int high(int i) {
		return ((i+1)<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits)-1;
	}
    void build(int[] v) {
        assert(v.length<(1<<n_bits));
        for(int i=0; i<(1<<n_bits); i++) {
            arr[i+(1<<n_bits)] = (i<v.length ? v[i] : inf);
        }
        for(int i=(1<<n_bits)-1; i>=1; i--) {
            arr[i] = Math.min(arr[2*i], arr[2*i+1]);
        }
        for(int i=0; i<(1<<(n_bits+1)); i++) {
            lazyadd[i] = 0;
        }
    }

    void decr(int left, int right) {
        node = 1;
        while(node != 0) {
            if(right>=high(node) && left<=low(node)) {
                lazyadd[node]--;
                while(node%2==0) {
                    arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
                    node = node/2;
                }
                node--;
            } else if(right<low(node) || left>high(node)) {
                while(node%2==0) {
                    arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
                    node = node/2;
                }
                node--;
            } else {
                node = node*2+1;
            }
        }
    }

    void pt_update(int x) {
        x += (1<<n_bits);
        arr[x] = (int)1e9;
        while(x!=0) {
            arr[x/2] = Math.min(arr[x]+lazyadd[x], arr[x^1]+lazyadd[x^1]);
            x = x/2;
        }
    }

    int find_zero() {
        node = 1;
        lazy = 0;
        if(lazyadd[1] + arr[1]!=0) return -1;
        while(node < (1<<n_bits)) {
            lazy += lazyadd[node];
            node *= 2;
            if(lazy + lazyadd[node] + arr[node] != 0) node++;
        }
        return node-(1<<n_bits);
    }
};

class plants {
	final int n_max = (int)2e5+5;
	int[] p_lt = new int[n_max];
	int[] p_rg = new int[n_max];
	int[] stash = new int[n_max]; // a manual queue
	int[] tallest = new int[n_max];
	int[] shortest = new int[n_max];
	void lexi_smallest(int k, int[] r, int[] ptr, int[] ord) {
		segtree s = new segtree();
		s.build(r);
		int n = r.length;
		stash[0] = n;
		ord[n] = -1;
		int front = 1;
		int back = 1;
		for(int i=0; i<r.length; i++) {
			int p = s.find_zero();
			while(p==-1) {
				s.decr(stash[front]-k+1+n, n-1);
				front++;
				p = s.find_zero();
			}
			ord[p] = i;
			s.pt_update(p);
			if(p<k-1) {
				s.decr(0, p);
				stash[back] = p;
				back++;
			} else {
				s.decr(p-k+1, p);
			}
			ptr[p] = ord[stash[front-1]];
		}
	}
	
	void init(int k, int[] r) {
		lexi_smallest(k, r, p_lt, tallest);
		for(int i=0; i<r.length; i++) {
			r[i] = k-1-r[i];
		}
		lexi_smallest(k, r, p_rg, shortest);
	}

	int compare_plants(int x, int y) {
		if(x>y) return -compare_plants(y,x);
		if(tallest[x]>tallest[y] || p_rg[y]>=shortest[x]) return -1;
		if(shortest[x]>shortest[y] || p_lt[y]>=tallest[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