제출 #1294198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294198		lambd47	식물 비교 (IOI20_plants)	C++20	0 / 100	164 ms	7964 KiB

plants

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

#define ll long long
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)

const int MX=2e5+7;
const int MOD=1e9+7;
const int LG=20;
pair<int,int> seg[4*MX];
int lz[4*MX];
vector<int> vec;
int n;
int lef[LG][MX];
int rig[LG][MX];

void refresh(int pos, int l, int r){
    if(lz[pos]==0)return;
    seg[pos].first+=lz[pos];
    if(l==r){
        lz[pos]=0;return;
    }
    lz[2*pos]+=lz[pos];
    lz[2*pos+1]+=lz[pos];
    lz[pos]=0;
}
void build(int pos, int ini, int fim){
    if(ini==fim){
        seg[pos]={vec[ini],ini};
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    build(e,ini,m);
    build(d,m+1,fim);
    seg[pos]=min(seg[e],seg[d]);
}
pair<int,int> query(int pos, int ini, int fim, int l, int r){
    refresh(pos,ini,fim);
    if(ini>r || fim<l)return make_pair(MOD,MOD);
    if(l<=ini && fim <=r)return seg[pos];
    int m=(ini+fim)/2;
    return min(query(2*pos,ini,m,l,r),query(2*pos+1,m+1,fim,l,r));
}
pair<int,int> query(int ini, int fim){
    if(ini<0)ini+=n;
    if(fim<0)fim+=n;
    if(fim>n)fim-=n;
    if(ini>n)ini-=n;
    if(ini<=fim){
        return query(1,0,n-1,ini,fim);
    }
    else{
        auto a=query(1,0,n-1,0,fim);
        auto b=query(1,0,n-1,ini,n-1);
        if(b.first<=a.first)return b;
        else return a;
    }
}
void update(int pos, int ini,int fim,int l, int r,int val){
    refresh(pos,ini,fim);
    if(ini>r || fim<l)return;
    if(l<= ini && fim <=r){
        lz[pos]+=val;
        refresh(pos,ini,fim);
        return;
    }
    int m=(ini+fim)/2;
    int e=2*pos,d=2*pos+1;
    update(e,ini,m,l,r,val);
    update(d,m+1,fim,l,r,val);
    seg[pos]=min(seg[e],seg[d]);
}
void update(int ini, int fim,int val){
    if(ini<0)ini+=n;
    if(fim<0)fim+=n;
    if(fim>n)fim-=n;
    if(ini>n)ini-=n;

    if(ini<=fim){
        update(1,0,n-1,ini,fim,val);
        return;
    }
    update(1,0,n-1,0,fim,val);
    update(1,0,n-1,ini,n-1,val);
}
bool pular(int a, int b){
    if(a==b)return true;
    int x=a;
    if(a<b){
        R(i,LG-1,0){
            if(rig[i][x]<=b && rig[i][x]>=x)x=rig[i][x];
        }
        if(x==b)return true;
    }
    else{
        R(i,LG-1,0){
            if(rig[i][x]>=x && rig[i][x]<n)x=rig[i][x];
        }
        x=rig[0][x];
        if(x<=b && pular(x,b))return true;
    }
    return false;
}
bool pulal(int a, int b){
    if(a==b)return true;
    int x=a;
    if(a>b){
        R(i,LG-1,0){
            if(lef[i][x]>=b && lef[i][x]<=x)x=lef[i][x];
        }
        if(x==b)return true;
    }
    else{
        R(i,LG-1,0){
            if(lef[i][x]>=0 && lef[i][x]<=x)x=lef[i][x];
        }
        x=lef[0][x];
        if(x>=b && pular(x,b))return true;
    }
    return false;
}
void init(int k, std::vector<int> A) {
    vec=A;
    n=sz(vec);
    build(1,0,n-1);
    queue<int> fila;
    L(i,0,n-1){
        if(vec[i]==0)fila.push(i);
    }
    vector<int> ord;
    vector<bool> marc(n);
    while(!fila.empty()){
        int a=fila.front();fila.pop();
        if(marc[a])continue;
        auto p=query(a-k+1,a-1);
        if(p.first==0)continue;
        ord.push_back(a);
        marc[a]=1;
        update(a-k+1,a-1,-1);
        if(p.first==1){
            fila.push(p.second);
        }
        update(a,a,MOD);
    }
    set<int> s;
    for(auto a:ord){
        s.insert(a);
        auto pt=s.find(a);
        pt++;
        rig[0][a]=lef[0][a]=a;
        if(pt==s.end()){
            auto ptaux=s.begin();
            int x=*ptaux;
            if(x+n-a<k)rig[0][a]=x;
        }else{
            int x=*pt;
            if(x-a<k)rig[0][a]=x;
        }
        pt--;
        if(pt==s.begin()){
            auto ptaux=s.end();
            ptaux--;
            int x=*ptaux;
            if(a+n-x<k)lef[0][a]=x;
        }
        else{
            pt--;
            int x=*pt;
            if(a-x<k)lef[0][a]=x;
        }
    }
    L(j,1,LG-1){
        L(i,0,n-1){
            lef[j][i]=lef[j-1][lef[j-1][i]];
            rig[j][i]=rig[j-1][rig[j-1][i]];
        }
    }
}

int compare_plants(int x, int y) {
    if(pulal(x,y)||pular(x,y))return -1;
    else if(pulal(y,x)||pular(y,x))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