oj.uz

Submission #640399

# Submission time Handle Problem Language Result Execution time Memory
640399 2022-09-14T14:32:37 Z lis05st Comparing Plants (IOI20_plants) C++17
5 / 100
 93 ms 41272 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=6e5;
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){
    push(v,l,r);
    if(r0<l||r<l0)return {1e9,1e9};
    if(l0<=l&&r<=r0)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);
    return get(2*v+1,m+1,r,l0,r0);
}

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-=2*n;r-=2*n;
    if(r>=0&&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;
    if(r>=0&&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;
    if(r>=0&&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;
    if(r>=0&&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;
    if(r>=0&&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;
    if(r>=0&&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);
    }
}

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;int R=n-1+n;
    if(2*k<=n)return;
    for(int step=n;step>=1;step--){
        auto[val,pos]=get(1,0,3*n-1,L,R);
        //cout<<"step: "<<step<<"\n";
        //cout<<val<<":"<<pos<<endl;
        if(get(1,0,3*n-1,pos-k+1,pos-1).first!=0){
            h[pos%n]=step;
            add(pos-k+1,pos-1,-1);
            add(pos,pos,1e9);
        }else{
            auto [val2,pos2]=get(1,0,3*n-1,pos-k+1,pos-1);
            h[pos2%n]=step;
            add(pos2-k+1,pos2-1,-1);
            add(pos2,pos2,1e9);
        }
    }
    //for(auto e:h)cout<<e<<" ";cout<<endl;
};
int compare_plants(int x, int y){
    if(k==2){
        x++,y++;
        if(zero(x,y-1))return 1;
        if(one(1,x-1)&&one(y,n))return 1;
        if(one(x,y-1))return -1;
        if(zero(1,x-1)&&zero(y,n))return -1;
        return 0;
    }
    if(h[x]>h[y])return 1;
    if(h[x]<h[y])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
    }
}*/

Subtask #1
5.0 / 5.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 46 ms 3088 KB Output is correct
7 Correct 53 ms 5820 KB Output is correct
8 Correct 87 ms 41072 KB Output is correct
9 Correct 89 ms 41188 KB Output is correct
10 Correct 92 ms 41192 KB Output is correct
11 Correct 93 ms 41224 KB Output is correct
12 Correct 89 ms 41144 KB Output is correct
13 Correct 82 ms 41244 KB Output is correct
14 Correct 87 ms 41272 KB Output is correct

Subtask #2
0 / 14.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 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 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 268 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 224 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 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 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 46 ms 3088 KB Output is correct
7 Correct 53 ms 5820 KB Output is correct
8 Correct 87 ms 41072 KB Output is correct
9 Correct 89 ms 41188 KB Output is correct
10 Correct 92 ms 41192 KB Output is correct
11 Correct 93 ms 41224 KB Output is correct
12 Correct 89 ms 41144 KB Output is correct
13 Correct 82 ms 41244 KB Output is correct
14 Correct 87 ms 41272 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Halted 0 ms 0 KB -