Submission #419191

#	Time	Username	Problem	Language	Result	Execution time	Memory
419191		79brue	Comparing Plants (IOI20_plants)	C++14	0 / 100	4083 ms	23032 KiB

plants

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

using namespace std;

typedef long long ll;

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

    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 NODE;
bool dist(int x, int y){
    x = (x+1 - NODE + n*10) % n;
    y = (y+1 - NODE + n*10) % n;

    if((x<k) ^ (y<k)) return y<k;
    return x<y;
}

struct mineSeg{
    struct Node {
        int lmax; int lidx;
        int rmax; int ridx;
        int ans; int ansl, ansr;
        int sum;

        Node(){}
        Node(ll x, int idx){
            lmax = rmax = ans = sum = x;
            lidx = ridx = ansl = ansr = idx;
        }

        Node merge(const Node &r)const{
            Node ret = *this;
            if(ret.lmax < sum + r.lmax){
                ret.lmax = sum + r.lmax;
                ret.lidx = r.lidx;
            }

            ret.rmax += r.sum;
            if(ret.rmax < r.rmax || (ret.rmax == r.rmax && dist(ret.ridx, r.ridx))){
                ret.rmax = r.rmax;
                ret.ridx = r.ridx;
            }

            if(ret.ans < r.ans || (ret.ans == r.ans && dist(ret.ansr, r.ansr))){
                ret.ans = r.ans, ret.ansl = r.ansl, ret.ansr = r.ansr;
            }
            if(ret.ans < rmax + r.lmax || (ret.ans == rmax+r.lmax && dist(ret.ansr, r.lidx))){
                ret.ans = rmax + r.lmax;
                ret.ansl = ridx, ret.ansr = r.lidx;
            }

            ret.sum += r.sum;
            ret.sum = max(ret.sum, (int)-1e9);
            return ret;
        }
    } tree[1600002];

    void init(int i, int l, int r, int *A){
        if(l==r){
            tree[i] = Node(A[l] ? 1 : -1e9, l);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i] = tree[i*2].merge(tree[i*2+1]);
    }

    void change(int i, int l, int r, int idx, int x){
        if(l==r){
            tree[i] = Node(x ? 1 : -1e9, l);
            return;
        }
        int m = (l+r)>>1;
        if(idx <= m) change(i*2, l, m, idx, x);
        else change(i*2+1, m+1, r, idx, x);
        tree[i] = tree[i*2].merge(tree[i*2+1]);
    }
} mineTree;

int arr[400002];
int sum[400002];
int ans[400002];
vector<int> bigger[5002];

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];
	for(int i=n+1; i<=n*2; i++) arr[i] = arr[i-n];

	for(int c=1; c<=n; c++){
        NODE = c;
        tree.init(1, 1, n*2, arr);
        mineTree.init(1, 1, n*2, arr);

        for(int turn=n; turn>=1; turn--){
            if(tree.findMin(1, 1, n*2, c, c).first == 0) break;
            auto tmp = mineTree.tree[1];
            if(tmp.ans < k-1) exit(1);
            int loc = tmp.ansr % n + 1;

            if(loc == c) break;
            bigger[c].push_back(loc);

            /// 1에서 0이 되는 위치들을 검색
            int lim = loc+n, leftmost = lim-k+1;
            while(leftmost < lim){
                pair<int, int> tmp2 = tree.findMin(1, 1, n*2, leftmost, lim-1);
                if(tmp2.first > 1) break;
                int x = tmp2.second;
                mineTree.change(1, 1, n*2, (x-1)%n+1, 0);
                mineTree.change(1, 1, n*2, (x-1)%n+1+n, 0);
                leftmost = x+1;
            }
            mineTree.change(1, 1, n*2, loc, 1);
            mineTree.change(1, 1, n*2, loc+n, 1);

            /// tree 변경
            tree.add(1, 1, n*2, loc, loc, 1000000000);
            tree.add(1, 1, n*2, loc+n, loc+n, 1000000000);

            if(loc >= k){
                tree.add(1, 1, n*2, loc-k+1, loc, -1);
                tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
            }
            else{
                tree.add(1, 1, n*2, 1, loc, -1);
                tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
                tree.add(1, 1, n*2, 2*n-(k-loc)+1, n*2, -1);
            }
        }

        for(int i=c+n-1; i>=c+n-k+1; i--){
            if(tree.findMin(1, 1, n*2, i, i).first) continue;
            int loc = (i-1)%n+1;
            bigger[c].push_back(loc);

            /// tree 변경
            tree.add(1, 1, n*2, loc, loc, 1000000000);
            tree.add(1, 1, n*2, loc+n, loc+n, 1000000000);

            if(loc >= k){
                tree.add(1, 1, n*2, loc-k+1, loc, -1);
                tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
            }
            else{
                tree.add(1, 1, n*2, 1, loc, -1);
                tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
                tree.add(1, 1, n*2, 2*n-(k-loc)+1, n*2, -1);
            }
        }
	}
}

int compare_plants(int x, int y) {
	x++, y++;
    if(find(bigger[x].begin(), bigger[x].end(), y) != bigger[x].end()) return -1;
    if(find(bigger[y].begin(), bigger[y].end(), x) != bigger[y].end()) return 1;
    return 0;
}

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