oj.uz

Submission #810872

# Submission time Handle Problem Language Result Execution time Memory
810872 2023-08-06T16:59:02 Z alvingogo Comparing Plants (IOI20_plants) C++14
0 / 100
 39 ms 3304 KB 
#include "plants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<pair<int,int> > st;
    void init(int x){
        st.resize(4*x);
    }
    void pull(int v){
        st[v].fs=min(st[2*v+1].fs,st[2*v+2].fs);
    }
    void upd(int v,int x){
        st[v].fs+=x;
        st[v].sc+=x;
    }
    void build(int v,int L,int R,vector<int>& x){
        if(L==R){
            st[v].fs=x[L];
            return;
        }
        int m=(L+R)/2;
        build(2*v+1,L,m,x);
        build(2*v+2,m+1,R,x);
        pull(v);
    }
    void pudo(int v){
        upd(2*v+1,st[v].sc);
        upd(2*v+2,st[v].sc);
        st[v].sc=0;
    }
    void update(int v,int L,int R,int l,int r,int t){
        if(L==l && R==r){
            upd(v,t);
            return;
        }
        pudo(v);
        int m=(L+R)/2;
        if(r<=m){
            update(2*v+1,L,m,l,r,t);
        }
        else if(l>m){
            update(2*v+2,m+1,R,l,r,t);
        }
        else{
            update(2*v+1,L,m,l,m,t);
            update(2*v+2,m+1,R,m+1,r,t);
        }
        pull(v);
    }
    int finds(int v,int L,int R){
        if(L==R){
            st[v].fs=1e9;
            return L;
        }
        if(st[v].fs>0){
            return -1;
        }
        int m=(L+R)/2;
        pudo(v);
        if(st[2*v+1].fs>0){
            return finds(2*v+2,m+1,R);
        }
        else{
            return finds(2*v+1,L,m);
        }
    }
};
int k;
int n;
vector<int> a[2];
void get(vector<int> c,int g){
    queue<int> s;
    ST st;
    int m=2*n;
    a[g].resize(m);
    st.init(m);
    st.build(0,0,m-1,c);
    for(int i=0;i<2*n;i++){
        int x=st.finds(0,0,m-1);
        while(x<0){
            auto h=s.front();
            s.pop();
            st.update(0,0,m-1,h,m-1,-1);
            x=st.finds(0,0,m-1);
        }
        int l=x-k+1;
        a[g][x]=i;
        if(l<0){
            st.update(0,0,m-1,0,x,-1);
            s.push(l+m);
        }
        else{
            st.update(0,0,m-1,l,x,-1);
        }
    }
}
void init(int K, vector<int> r){
    k=K;
    n=r.size();
    vector<int> z(2*n);
    for(int i=0;i<n;i++){
        z[i]=z[i+n]=r[i];
    }
    get(z,0);
    for(auto& h:z){
        h=k-1-h;
    }
    get(z,1);
}

int compare_plants(int x, int y) {
    if(x>y){
        return -compare_plants(y,x);
    }
    if(a[0][x]>a[0][y] || a[1][y]>a[1][x+n]){
        return -1;
    }
    else if(a[1][x]>a[1][y] || a[0][y]>a[0][x+n]){
        return 1;
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 39 ms 3304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -