oj.uz

Submission #641766

# Submission time Handle Problem Language Result Execution time Memory
641766 2022-09-17T15:03:24 Z lis05st Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 321724 KB 
#ifdef LIS05ST
    #define _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG_PEDANTIC
#endif
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt")
#include"plants.h"
#include"bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;

const int NMAX=2e6;
int pref[NMAX+5];
int n,k;

int get(int l,int r){
    return pref[r]-pref[l-1];
}
bool one(int l,int r){
    return get(l,r)==r-l+1;
}
bool zero(int l,int r){
    return get(l,r)==0;
}
vector<int>h;
int id(int x){
    return (x%n+n)%n;
}


struct Node{
    int min;
    int pos;
    ll padd;
};
Node tree[4*NMAX+5];

Node merge(Node a,Node b){
    Node res;
    res.min=min(a.min,b.min);
    res.pos=-1;
    if(a.min==res.min){
        res.pos=max(res.pos,a.pos);
    }
    if(b.min==res.min){
        res.pos=max(res.pos,b.pos);
    }
    res.padd=0;
    return res;
}

vector<int>vec;
void build(int v,int l,int r){
    if(l==r){
        tree[v].min=vec[l];
        tree[v].pos=l;
        tree[v].padd=0;
        return;
    }
    int m=(l+r)/2;
    build(2*v,l,m);
    build(2*v+1,m+1,r);
    tree[v]=merge(tree[2*v],tree[2*v+1]);
}

void pushAdd(int v,int val){
    tree[v].min+=val;
    tree[v].padd+=val;
}
void push(int v,int l,int r){
    pushAdd(2*v,tree[v].padd);
    pushAdd(2*v+1,tree[v].padd);
    tree[v].padd=0;
}

pair<int,int> get(int v,int l,int r,int l0,int r0,bool p=1){
    //if(p)cout<<l<<":"<<r<<" "<<l0<<":"<<r0<<"\n";
    //if(p)cout<<tree[2*v].min<<" "<<tree[2*v].pos<<"\n";
    push(v,l,r);
    if(r0<l||r<l0||tree[v].min!=0)return {1e9,1e9};
    if(l0<=l&&r<=r0&&l==r)return {tree[v].min,tree[v].pos};
    int m=(l+r)/2;
    if(tree[2*v].min==0&&tree[2*v].pos>=l0)return get(2*v,l,m,l0,r0,p);
    return get(2*v+1,m+1,r,l0,r0,p);
}

void add(int v,int l,int r,int l0,int r0,int val){
    push(v,l,r);
    if(r0<l||r<l0)return;
    if(l0<=l&&r<=r0){
        pushAdd(v,val);
        return;
    }
    int m=(l+r)/2;
    add(2*v,l,m,l0,r0,val);
    add(2*v+1,m+1,r,l0,r0,val);
    tree[v]=merge(tree[2*v],tree[2*v+1]);
}

void add(int l,int r,int val){
    l-=3*n;r-=3*n;
    for(auto e:vector<int>{0,1,2,3,4,5,6,7,8}){
        if(0<=r&&r<=3*n-1){
            int L=min(3*n-1,max(l,0));
            int R=min(3*n-1,max(r,0));
            add(1,0,3*n-1,L,R,val);
        }
        else if(0<=l&&l<=3*n-1){
            int L=min(3*n-1,max(l,0));
            int R=min(3*n-1,max(r,0));
            add(1,0,3*n-1,L,R,val);
        }
        l+=n;r+=n;
    }
}
int step;
void extract(int pos){
    while(true){
        auto [a,b]=get(1,0,3*n-1,pos-k+1,pos-1);
        if(a==0)extract(b);
        else break;
    }

    h[pos%n]=step--;
    add(pos-k+1,pos-1,-1);
    add(pos,pos,1e9);
}


int lefte[30][NMAX+5];
int righte[30][NMAX+5];


void init(int K, std::vector<int> rr){
    n=rr.size();h.resize(n);
    k=K;
    for(int i=0;i<n;i++)pref[i+1]=pref[i]+rr[i];

    for(int e=0;e<3;e++)for(int i=0;i<n;i++){
        vec.push_back(rr[i]);
    }
    //for(auto e:vec)cout<<e<<" ";cout<<"\n";
    build(1,0,3*n-1);
    int L=0+n+n;int R=n-1+n+n;
    step=n;
    while(step>=1){

        auto[val,pos]=get(1,0,3*n-1,L,R);
        extract(pos);
    }
    for(int i=0;;i++){
        if(h.size()==5*n)break;
        h.push_back(h[i]);
    }
    //for(auto e:h)cout<<e<<" ";cout<<"\n";
    set<pair<int,int>,greater<pair<int,int>>>st;
    int N=5*n;
    for(int i=0;i<N;i++){
        if(i-1>=0)st.insert({h[i-1],i-1});
        if(i-k>=0)st.erase({h[i-k],i-k});
        if(st.empty())lefte[0][i]=i;
        else if(st.begin()->first>=h[i])lefte[0][i]=i;
        else lefte[0][i]=st.begin()->second;
    }
    st.clear();
    for(int i=N-1;i>=0;i--){
        if(i+1<N)st.insert({h[i+1],i+1});
        if(i+k<N)st.erase({h[i+k],i+k});
        if(st.empty())righte[0][i]=i;
        else if(st.begin()->first>=h[i])righte[0][i]=i;
        else righte[0][i]=st.begin()->second;
    }
    for(int lvl=1;lvl<30;lvl++){
        for(int i=0;i<N;i++){
            lefte[lvl][i]=lefte[lvl-1][lefte[lvl-1][i]];
            righte[lvl][i]=righte[lvl-1][righte[lvl-1][i]];
        }
    }
};

int ddist(int u,int v){
    return min({abs(u-v),abs(u+n-v),abs(v+n-u)});
}

int lgt(int x,int y){
    for(int lvl=29;lvl>=0;lvl--){
        int pos=lefte[lvl][x];
        if(pos<y)continue;
        x=pos;
    }
    if(ddist(x,y)<k&&h[x]>=h[y])return 1;
    return 0;
}
int rgt(int x,int y){
    for(int lvl=29;lvl>=0;lvl--){
        int pos=righte[lvl][x];
        if(pos>y)continue;
        x=pos;
    }
    if(ddist(x,y)<k&&h[x]>=h[y])return 1;
    return 0;
}

int gt(int X,int y){
    while(X-n>=0)X-=n;
    while(y-n>=0)y-=n;
    for(int x=X;x<5*n;x+=n){
        if(x<y)if(rgt(x,y))return 1;
        if(y<x)if(lgt(x,y))return 1;
        while(y-n>=0){
            y-=n;
            if(x<y)if(rgt(x,y))return 1;
            if(y<x)if(lgt(x,y))return 1;
        }

        if(x<y)if(rgt(x,y))return 1;
        if(y<x)if(lgt(x,y))return 1;
        while(y+n<5*n){
            y+=n;
            if(x<y)if(rgt(x,y))return 1;
            if(y<x)if(lgt(x,y))return 1;
        }
    }
    return 0;
}

int compare_plants(int x, int y){
    if(gt(x,y))return 1;
    if(gt(y,x))return -1;
    return 0;
}

#define MULTITESTS false
void solve(int testCase){

}

           
//   x     y


void precalc(){

}
/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    precalc();
    int t=1;
    if(MULTITESTS)cin>>t;
    for(int i=1;i<=t;i++){
        auto t1=clock();
        solve(i);
        auto t2=clock();
        float delta=t2-t1;
        delta/=CLOCKS_PER_SEC;
        #ifdef LIS05ST
        cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
        #endif
    }
}*/

Compilation message

plants.cpp: In function 'void add(int, int, int)':
plants.cpp:104:14: warning: unused variable 'e' [-Wunused-variable]
  104 |     for(auto e:vector<int>{0,1,2,3,4,5,6,7,8}){
      |              ^
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:154:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  154 |         if(h.size()==5*n)break;
      |            ~~~~~~~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1183 ms 4500 KB Output is correct
7 Execution timed out 4046 ms 33952 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 26 ms 2424 KB Output is correct
7 Correct 1343 ms 12736 KB Output is correct
8 Correct 16 ms 980 KB Output is correct
9 Correct 28 ms 2508 KB Output is correct
10 Correct 1503 ms 12776 KB Output is correct
11 Correct 117 ms 12668 KB Output is correct
12 Correct 2109 ms 12832 KB Output is correct
13 Correct 1327 ms 12780 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 26 ms 2424 KB Output is correct
7 Correct 1343 ms 12736 KB Output is correct
8 Correct 16 ms 980 KB Output is correct
9 Correct 28 ms 2508 KB Output is correct
10 Correct 1503 ms 12776 KB Output is correct
11 Correct 117 ms 12668 KB Output is correct
12 Correct 2109 ms 12832 KB Output is correct
13 Correct 1327 ms 12780 KB Output is correct
14 Correct 3494 ms 34692 KB Output is correct
15 Execution timed out 4034 ms 321724 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 708 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Incorrect 17 ms 2260 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1183 ms 4500 KB Output is correct
7 Execution timed out 4046 ms 33952 KB Time limit exceeded
8 Halted 0 ms 0 KB -