제출 #434657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434657		79brue	식물 비교 (IOI20_plants)	C++14	32 / 100	2722 ms	149864 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;

struct mineSeg{
    struct Node {
        ll lmax; int lidx;
        ll rmax; int ridx;
        ll ans; int ansl, ansr;
        ll 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;
                ret.ridx = r.ridx;
            }

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

            ret.sum += r.sum;
            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;

struct checkSeg{
    int tree[1600002];

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

    void update(int i, int l, int r, int idx, int val){
        if(l==r){
            tree[i] = val;
            return;
        }
        int m = (l+r)>>1;
        if(idx <= m) update(i*2, l, m, idx, val);
        else update(i*2+1, m+1, r, idx, val);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} chkseg;

int n, k;
int arr[400002];
int sum[400002];
int ans[400002];
int ord[400002];
int L[400002], R[400002];
int Lsp[400002][20], Rsp[400002][20];
int Lg[400002][20], Rg[400002][20];

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];

    tree.init(1, 1, n*2, arr);
    mineTree.init(1, 1, n*2, arr);

    for(int turn=n; turn>=1; turn--){
        auto tmp = mineTree.tree[1];
        if(tmp.ans < k-1) exit(1);
        int loc = tmp.ansr % n + 1;
        ans[loc] = turn;
        ord[turn] = 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);
        }
    }

    chkseg.init(1, 1, n*2);
    for(int turn=1; turn<=n; turn++){
        int x = ord[turn];

        L[turn] = chkseg.query(1, 1, n*2, x+n-(k-1), x+n);
        R[turn] = chkseg.query(1, 1, n*2, x, x+(k-1));

        chkseg.update(1, 1, n*2, x, turn);
        chkseg.update(1, 1, n*2, x+n, turn);
    }

    for(int i=1; i<=n; i++){
        Lsp[i][0] = L[i], Rsp[i][0] = R[i];
        if(ord[i] < ord[L[i]]) Lg[i][0] = -1;
        if(ord[i] > ord[R[i]]) Rg[i][0] = 1;
    }
    for(int d=1; d<20; d++){
        for(int i=1; i<=n; i++){
            Lsp[i][d] = Lsp[Lsp[i][d-1]][d-1];
            Rsp[i][d] = Rsp[Rsp[i][d-1]][d-1];
            Lg[i][d] = Lg[i][d-1] + Lg[Lsp[i][d-1]][d-1];
            Rg[i][d] = Rg[i][d-1] + Rg[Rsp[i][d-1]][d-1];
        }
    }
}

int compare_plants(int x, int y) {
	x++, y++;
	int def = ans[x] > ans[y] ? 1 : -1;
	if(ans[x] < ans[y]) swap(x, y);

	int tmp = ans[x];
	ll lLim=0, rLim=0;
    for(int d=19; d>=0; d--){
        if(Lsp[tmp][d] == 0 || Lsp[tmp][d] < ans[y]) continue;
        lLim += Lg[tmp][d];
        tmp = Lsp[tmp][d];
    }
    lLim += ord[tmp];

    tmp = ans[x];
    for(int d=19; d>=0; d--){
        if(Rsp[tmp][d] == 0 || Rsp[tmp][d] < ans[y]) continue;
        rLim += Rg[tmp][d];
        tmp = Rsp[tmp][d];
    }
    rLim += ord[tmp];

    ll l = lLim, r = rLim;
    if((r-l) >= n) return def;

    l = (n - (-l%n))%n;
    if(!l) l=n;

    r = (n - (-r%n))%n;
    if(!r) r=n;
    if(r<l) r+=n;

    if(l<=y && y<=r) return def;
    if(l<=y+n && y+n<=r) return def;
    return 0;
}

• Subtask 1: 5 / 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