제출 #1231277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231277		Hamed_Ghaffari	Comparing Plants (IOI20_plants)	C++20	100 / 100	743 ms	79208 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define mins(a, b) (a = min(a, b))

const int MXN = 2e5+5;
const int LOG = 19;

int n, k, lz[MXN<<2];
pii seg[MXN<<2];

void build(int l=0, int r=n, int id=1) {
    seg[id] = {0, l};
    if(r-l == 1) return;
    build(l, mid, lc);
    build(mid, r, rc);
}
inline void apply(int x, int id) {
    seg[id].X += x;
    lz[id] += x;
}
inline void push(int id) {
    if(lz[id]) {
        apply(lz[id], lc);
        apply(lz[id], rc);
        lz[id] = 0;
    }
}
void upd(int s, int e, int x, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) {
        apply(x, id);
        return;
    }
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    seg[id] = min(seg[lc], seg[rc]);
}
pii get(int s, int e, int l=0, int r=n, int id=1) {
    if(s>=r || l>=e) return pii(n, n);
    if(s<=l && r<=e) return seg[id];
    push(id);
    return min(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}

int pos[MXN], timer;
vector<int> ord;

namespace seg2 {
    pii seg[MXN<<2];
    void build(int l=0, int r=n, int id=1) {
        seg[id] = {n+1, r-1};
        if(r-l == 1) return;
        build(l, mid, lc);
        build(mid, r, rc);
    }
    void upd(int p, int x, int l=0, int r=n, int id=1) {
        seg[id] = {x, p};
        if(r-l == 1) return;
        p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
    }
    pii get(int s, int e, int l=0, int r=n, int id=1) {
        if(s>=r || l>=e) return pii(n+1, 0);
        if(s<=l && r<=e) return seg[id];
        return min(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
    }
}

void rec(int i) {
    while(1) {
        pii d = i-k+1>=0 ? get(i-k+1, i) : min(get(0, i), get(n+(i-k+1), n));
        if(d.X) break;
        rec(d.Y);
    }
    ord.push_back(i);
    pos[i] = ++timer;
    if(i-k+1>=0) upd(i-k+1, i, -1);
    else upd(0, i, -1), upd(n+(i-k+1), n, -1);
    upd(i, i+1, n);
}


int lft[MXN<<1][LOG], rgt[MXN<<1][LOG], lft_[MXN], rgt_[MXN];

void init(int k, vector<int> r) {
    ::k = k;
    n = r.size();
    build();
    for(int i=0; i<n; i++) upd(i, i+1, r[i]);
    while(seg[1].X==0)
        rec(seg[1].Y);
    
    seg2::build();
    reverse(ord.begin(), ord.end());
    memset(lft_, -1, sizeof(lft_));
    memset(rgt_, -1, sizeof(rgt_));
    for(int i : ord) {
        pii d = {n+1, 0};
        if(i-k+1>=0) mins(d, seg2::get(i-k+1, i));
        else mins(d, seg2::get(0, i)), mins(d, seg2::get(n+(i-k+1), n));
        if(d.X!=n+1) lft_[i] = d.Y;
        d = {n+1, 0};
        if(i+k-1<n) mins(d, seg2::get(i+1, i+k));
        else mins(d, seg2::get(i+1, n)), mins(d, seg2::get(0, k-1-(n-(i+1))));
        if(d.X!=n+1) rgt_[i] = d.Y;
        seg2::upd(i, pos[i]);
    }

    lft[0][0] = 0;
    rgt[2*n+1][0] = 2*n+1;
    for(int i=0; i<n; i++) {
        if(lft_[i]==-1) lft[i+1][0] = 0, lft[i+1+n][0] = 0;
        else if(lft_[i]<i) lft[i+1][0] = lft_[i]+1, lft[i+1+n][0] = lft_[i]+1+n;
        else lft[i+1][0] = 0, lft[i+1+n][0] = lft_[i]+1;

        if(rgt_[i]==-1) rgt[i+1][0] = 2*n+1, rgt[i+1+n][0] = 2*n+1;
        else if(rgt_[i]>i) rgt[i+1][0] = rgt_[i]+1, rgt[i+1+n][0] = rgt_[i]+1+n;
        else rgt[i+1][0] = rgt_[i]+1+n, rgt[i+1+n][0] = 2*n+1;
    }

    for(int j=1; j<LOG; j++)
        for(int i=0; i<=2*n+1; i++)
            lft[i][j] = lft[lft[i][j-1]][j-1],
            rgt[i][j] = rgt[rgt[i][j-1]][j-1];
}

int compare_plants(int x, int y) {
    int z = 1;

    for(int t : {0, 1}) {
        int i=x+1, j=x<y?y+1:y+1+n;
        for(int b=LOG-1; b>=0; b--)
            if(rgt[i][b]<j)
                i = rgt[i][b];
        if(j-i<k && pos[(i-1)%n]<pos[(j-1)%n]) return z;
        i = x+1;
        for(int b=LOG-1; b>=0; b--)
            if(lft[j][b]>i)
                j = lft[j][b];
        if(j-i<k && pos[(j-1)%n]<pos[(i-1)%n]) return -z;

        z = -z;
        swap(x, y);
    }

    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