oj.uz

답안 #1008718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1008718 2024-06-26T16:57:39 Z bachhoangxuan 식물 비교 (IOI20_plants) C++17
14 / 100
 579 ms 111072 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxl = 25;
const int inf = 1e9;
int n,k;
vector<int> R,H;
set<int> ss,cc;
int lt[maxn][maxl],rt[maxn][maxl];

void cal(int x,int y){
    cc.erase(y);
    if((y-x+n)%n>=k){
        cc.insert(y);
    }
}
void add(int x){
    if(ss.empty()){
        ss.insert(x);
        cc.insert(x);
        return;
    }
    auto it=ss.lower_bound(x);
    if(it!=ss.end()) cal(x,*it);
    else cal(x,*ss.begin());
    if(it==ss.begin()) cal(*ss.rbegin(),x);
    else{
        it--;
        cal(*it,x);
    }
    ss.insert(x);
}
void del(int x){
    cc.erase(x);ss.erase(x);
    if(ss.empty()) return;
    auto it=ss.lower_bound(x);
    int y=(it!=ss.end()?*it:*ss.begin());
    cc.insert(y);
}

int tree[4*maxn],lazy[4*maxn];
void build(int l,int r,int id){
    lazy[id]=0;
    if(l==r){
        tree[id]=R[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);build(mid+1,r,id<<1|1);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
void getnew(int id,int val){
    tree[id]-=val;
    lazy[id]+=val;
}
void pushdown(int id){
    if(!lazy[id]) return;
    getnew(id<<1,lazy[id]);
    getnew(id<<1|1,lazy[id]);
    lazy[id]=0;
}
void get(int l,int r,int id){
    if(tree[id]>0) return;
    if(l==r){
        tree[id]=inf;
        add(l);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    get(l,mid,id<<1);get(mid+1,r,id<<1|1);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
void update(int l,int r,int id,int tl,int tr){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        getnew(id,1);
        return;
    }
    pushdown(id);
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr);update(mid+1,r,id<<1|1,tl,tr);
    tree[id]=min(tree[id<<1],tree[id<<1|1]);
}
vector<int> solve(vector<int> r){
    R=r;
    vector<int> p(n);
    ss.clear();cc.clear();
    build(0,n-1,1);
    for(int i=n-1;i>=0;i--){
        get(0,n-1,1);
        int x=*cc.begin();
        if((int)cc.size()>1 && x==0) x=*cc.rbegin();
        p[x]=i;del(x);
        if(x>=k-1) update(0,n-1,1,x-k+1,x);
        else{
            update(0,n-1,1,0,x);
            update(0,n-1,1,n-(k-x)+1,n-1);
        }
    }
    return p;
}

void init(int _k, std::vector<int> r) {
    k=_k;
    n=(int)r.size();
    H=solve(r);

    set<pair<int,int>> S;
    for(int i=0;i<k;i++) S.insert({H[i],i});
    for(int i=0;i<n;i++){
        auto it=S.erase(S.lower_bound({H[i],i}));
        if(it!=S.begin()) it=prev(it),rt[i][0]=(it->second-i+n)%n;
        S.insert({H[(i+k)%n],(i+k)%n});
    }
    S.clear();
    for(int i=1;i<=k;i++) S.insert({H[(n-i)%n],(n-i)%n});
    for(int i=0;i<n;i++){
        S.erase({H[(i-k+n)%n],(i-k+n)%n});
        auto it=S.insert({H[i],i}).first;
        if(it!=S.begin()) it=prev(it),lt[i][0]=(i-it->second+n)%n;
    }
    for(int j=1;j<18;j++){
        for(int i=0;i<n;i++){
            int nr=(i+rt[i][j-1])%n;
            assert(0<=nr && nr<n);
            rt[i][j]=rt[i][j-1]+rt[nr][j-1];
            int nl=(i-lt[i][j-1]%n+n)%n;
            assert(0<=nl && nl<n);
            lt[i][j]=lt[i][j-1]+lt[nl][j-1];
        }
    }
}

bool get_lt(int x,int y){
    int d=(x-y+n)%n;
    for(int i=17;i>=0;i--){
        if(lt[x][i]<=d) d-=lt[x][i],x=(x-lt[x][i]%n+n)%n;
    }
    return (x-y+n)%n<k && H[x]>=H[y];
}

bool get_rt(int x,int y){
    int d=(y-x+n)%n;
    for(int i=17;i>=0;i--){
        if(rt[x][i]<=d) d-=rt[x][i],x=(x+rt[x][i])%n;
    }
    return (y-x+n)%n<k && H[x]>=H[y];
}

int compare_plants(int x, int y) {
    /*
    if(get_lt(x,y) || get_rt(x,y)) return 1;
    if(get_lt(y,x) || get_rt(y,x)) return -1;
	return 0;
	*/
    return (H[x]>H[y]?1:-1);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 35 ms 4432 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 37 ms 4616 KB Output is correct
11 Correct 34 ms 4464 KB Output is correct
12 Correct 38 ms 4692 KB Output is correct
13 Correct 43 ms 4520 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 35 ms 4432 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 37 ms 4616 KB Output is correct
11 Correct 34 ms 4464 KB Output is correct
12 Correct 38 ms 4692 KB Output is correct
13 Correct 43 ms 4520 KB Output is correct
14 Correct 65 ms 8500 KB Output is correct
15 Runtime error 579 ms 111072 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 32 ms 3580 KB Output is correct
4 Correct 217 ms 52128 KB Output is correct
5 Correct 268 ms 49732 KB Output is correct
6 Correct 310 ms 49144 KB Output is correct
7 Correct 354 ms 49476 KB Output is correct
8 Runtime error 500 ms 107972 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -