제출 #431778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
431778		Peti	식물 비교 (IOI20_plants)	C++14	49 / 100	1721 ms	28836 KiB

plants

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

using namespace std;

const int maxn = 1<<18;

pair<int, int> st[maxn<<1];
int add[maxn<<1] = {};

void prop(int x){
    if(x < maxn){
        add[2*x] += add[x];
        st[2*x].first += add[x];
        add[2*x+1] += add[x];
        st[2*x+1].first += add[x];
    }
    add[x] = 0;
}

inline void upd(int &x){
    if(x < maxn) st[x] = min(st[2*x], st[2*x+1]);
}

void build(vector<int> &v){
    for(int i = 0; i < (int)v.size(); i++)
        st[maxn+i] = make_pair(v[i], i);
    for(int i = maxn-1; i > 0; i--)
        upd(i);
}

void kivesz(int ind, int x, int l, int r){
    prop(x);
    if(l+1 == r){
        st[x].first = (int)1e9;
        return;
    }
    int m = (l+r)/2;
    if(ind < m)
        kivesz(ind, 2*x, l, m);
    else
        kivesz(ind, 2*x+1, m, r);
    upd(x);
}

void update(int s, int e, int x, int l, int r){
    prop(x);
    if(e <= l || r <= s)
        return;
    if(s <= l && r <= e){
        st[x].first--;
        add[x]--;
        return;
    }
    int m = (l+r)/2;
    update(s, e, 2*x, l, m);
    update(s, e, 2*x+1, m, r);
    upd(x);
}

void update(int l, int r, int n){
    if(l > r){
        update(l, n, 1, 0, maxn);
        update(0, r, 1, 0, maxn);
    } else
        update(l, r, 1, 0, maxn);
}

pair<int, int> keres(int s, int e, int x, int l, int r){
    prop(x);
    if(e <= l || r <= s)
        return make_pair((int)1e9, 0);
    if(s <= l && r <= e)
        return st[x];
    int m = (l+r)/2;
    return min(keres(s, e, 2*x, l, m), keres(s, e, 2*x+1, m, r));
}

int keres(int l, int r, int n){
    if(r < l){
        pair<int, int> temp = keres(l, n, 1, 0, maxn);
        //cout<<temp.first<<" keres first\n";
        if(temp.first == 0)
            return temp.second;
        temp = keres(0, r, 1, 0, maxn);
        //cout<<temp.first<<" keres second\n";
        if(temp.first == 0)
            return temp.second;
        return -1;
    }
    pair<int, int> temp = keres(l, r, 1, 0, maxn);
    //cout<<temp.first<<" keres one\n";
    if(temp.first == 0)
        return temp.second;
    return -1;
}

struct node{
    int l = -1, r = -1;
    long long lc, rc;
};

vector<node> g;
vector<int> vh;
int n;

void init(int k, std::vector<int> r) {
    n = (int)r.size();
    g.resize(n);
    vh.resize(n);
    for(int &x : r)
        x = k-x-1;
    build(r);

    int x = keres(0, n, n), h = 0;
    vector<int> sor;
    while(x != -1){
        int y = keres((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
        while(y != -1){
            x = y;
            y = keres((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
        }
        //cout<<"x: "<<x<<"\n";
        vh[x] = h++;
        sor.push_back(x);
        update((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
        kivesz(x, 1, 0, maxn);
        x = keres(x+1, x, n);
    }

    /*cout<<"h: ";
    for(int x : vh)
        cout<<x<<" ";
    cout<<"\n";*/

    set<pair<int, int>, greater<pair<int, int>>> nums;
    for(int i = n-k+1; i < n; i++)
        nums.insert(make_pair(vh[i], i));
    for(int i = 0; i < n; i++){
        auto it = nums.lower_bound(make_pair(vh[i], i));
        if(it != nums.end())
            g[i].l = it->second;

        int j = i-k+1;
        if(j < 0) j += n;
        nums.erase(make_pair(vh[j], j));
        nums.insert(make_pair(vh[i], i));
    }
    nums.clear();
    for(int i = 0; i < k-1; i++)
        nums.insert(make_pair(vh[i], i));
    for(int i = n-1; i >= 0; i--){
        auto it = nums.lower_bound(make_pair(vh[i], i));
        if(it != nums.end())
            g[i].r = it->second;

        int j = i+k-1;
        if(j >= n) j -= n;
        nums.erase(make_pair(vh[j], j));
        nums.insert(make_pair(vh[i], i));
    }

    for(int x : sor){
        g[x].lc = x - g[x].l;
        if(g[x].lc < 0) g[x].lc += n;
        g[x].rc = g[x].r - x;
        if(g[x].rc < 0) g[x].rc += n;
        if(g[x].l != -1)
            g[x].lc += g[g[x].l].lc;
        else
            g[x].lc = 0;
        if(g[x].r != -1)
            g[x].rc += g[g[x].r].rc;
        else
            g[x].rc = 0;
    }

    /*for(int i = 0; i < n; i++)
        cout<<"pont "<<i<<": "<<g[i].l<<" "<<g[i].r<<" | "<<g[i].lc<<" "<<g[i].rc<<"\n";*/

	return;
}

bool benne(long long l1, long long r1, long long l2, long long r2){
    return l1 <= l2 && r2 <= r1;
}

int compare_plants(int x, int y) {
    int ret = 1;
    if(vh[x] < vh[y]){
        ret = -1;
        swap(x, y);
    }
    long long l1 = (long long)x - g[x].lc, r1 = (long long)x + g[x].rc, l2 = (long long)y - g[y].lc, r2 = (long long)y + g[y].rc;
    if(benne(l1, r1, l2, r2) || benne(l1, r1, l2-n, r2-n) || benne(l1, r1, l2+n, r2+n))
        return ret;
    return 0;
}

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