oj.uz

Submission #640398

# Submission time Handle Problem Language Result Execution time Memory
640398 2022-09-14T14:32:03 Z lis05st Comparing Plants (IOI20_plants) C++17
5 / 100
 117 ms 43588 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;
    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 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 Correct 1 ms 212 KB Output is correct
6 Correct 50 ms 3060 KB Output is correct
7 Correct 56 ms 5808 KB Output is correct
8 Correct 94 ms 41072 KB Output is correct
9 Correct 114 ms 42352 KB Output is correct
10 Correct 95 ms 42384 KB Output is correct
11 Correct 90 ms 42424 KB Output is correct
12 Correct 96 ms 42424 KB Output is correct
13 Correct 81 ms 42356 KB Output is correct
14 Correct 117 ms 43588 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 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 1 ms 212 KB Output is correct
3 Incorrect 1 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 1 ms 212 KB Output is correct
2 Incorrect 0 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 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 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 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 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 Correct 1 ms 212 KB Output is correct
6 Correct 50 ms 3060 KB Output is correct
7 Correct 56 ms 5808 KB Output is correct
8 Correct 94 ms 41072 KB Output is correct
9 Correct 114 ms 42352 KB Output is correct
10 Correct 95 ms 42384 KB Output is correct
11 Correct 90 ms 42424 KB Output is correct
12 Correct 96 ms 42424 KB Output is correct
13 Correct 81 ms 42356 KB Output is correct
14 Correct 117 ms 43588 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Halted 0 ms 0 KB -