제출 #419094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419094		79brue	Comparing Plants (IOI20_plants)	C++14	27 / 100	567 ms	16788 KiB

plants

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

using namespace std;

typedef long long ll;

struct segTree{
    pair<int, int> tree[800002];
    int lazy[800002];

    void init(int i, int l, int r, int *A){
        lazy[i] = 0;
        if(l==r){
            tree[i] = make_pair(A[l], l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    void propagate(int i, int l, int r){
        tree[i].first += lazy[i];
        if(l!=r){
            lazy[i*2] += lazy[i];
            lazy[i*2+1] += lazy[i];
        }
        lazy[i] = 0;
    }

    void add(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        add(i*2, l, m, s, e, val);
        add(i*2+1, m+1, r, s, e, val);
        tree[i] = min(tree[i*2], tree[i*2+1]);
    }

    pair<int, int> findMin(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return make_pair(INT_MAX, INT_MAX);
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return min(findMin(i*2, l, m, s, e), findMin(i*2+1, m+1, r, s, e));
    }
} tree;

int n, k;
int arr[200002];
int sum[200002];
int ans[200002];

void init(int _k, vector<int> r) {
	n = (int)r.size();
	k = _k;
	for(int i=1; i<=n; i++) arr[i] = r[i-1];

    tree.init(1, 1, n, arr);

    for(int turn=n; turn>=1; turn--){
        int minLoc = tree.findMin(1, 1, n, 1, n).second;
        if(minLoc < k){
            auto tmp = tree.findMin(1, 1, n, n-(k-minLoc)+1, n);
            if(tmp.first == 0) minLoc = tmp.second;
        }

        ans[minLoc] = turn;
        tree.add(1, 1, n, minLoc, minLoc, 1000000000);
        if(minLoc >= k) tree.add(1, 1, n, minLoc-k+1, minLoc, -1);
        else{
            tree.add(1, 1, n, 1, minLoc, -1);
            tree.add(1, 1, n, n-(k-minLoc)+1, n, -1);
        }
    }
}

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

	if(ans[x] > ans[y]) return 1;
	return -1;
}

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