oj.uz

Submission #641770

# Submission time Handle Problem Language Result Execution time Memory
641770 2022-09-17T15:06:58 Z lis05st Comparing Plants (IOI20_plants) C++17
32 / 100
 3459 ms 183752 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()==3*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=3*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<21;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=20;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=20;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<3*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<3*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()==3*n)break;
      |            ~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 290 ms 3432 KB Output is correct
7 Correct 1099 ms 18320 KB Output is correct
8 Correct 3161 ms 175960 KB Output is correct
9 Correct 3215 ms 176012 KB Output is correct
10 Correct 2859 ms 175796 KB Output is correct
11 Correct 2508 ms 175928 KB Output is correct
12 Correct 2286 ms 175800 KB Output is correct
13 Correct 829 ms 175880 KB Output is correct
14 Correct 2407 ms 175888 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 344 ms 7252 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 10 ms 1444 KB Output is correct
10 Correct 316 ms 7252 KB Output is correct
11 Correct 84 ms 7180 KB Output is correct
12 Correct 509 ms 7308 KB Output is correct
13 Correct 333 ms 7296 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 344 ms 7252 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 10 ms 1444 KB Output is correct
10 Correct 316 ms 7252 KB Output is correct
11 Correct 84 ms 7180 KB Output is correct
12 Correct 509 ms 7308 KB Output is correct
13 Correct 333 ms 7296 KB Output is correct
14 Correct 769 ms 18556 KB Output is correct
15 Correct 3393 ms 180184 KB Output is correct
16 Correct 821 ms 18536 KB Output is correct
17 Correct 3459 ms 180168 KB Output is correct
18 Correct 1160 ms 179124 KB Output is correct
19 Correct 3431 ms 178960 KB Output is correct
20 Correct 3112 ms 183752 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 608 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 0 ms 596 KB Output is correct
6 Correct 290 ms 3432 KB Output is correct
7 Correct 1099 ms 18320 KB Output is correct
8 Correct 3161 ms 175960 KB Output is correct
9 Correct 3215 ms 176012 KB Output is correct
10 Correct 2859 ms 175796 KB Output is correct
11 Correct 2508 ms 175928 KB Output is correct
12 Correct 2286 ms 175800 KB Output is correct
13 Correct 829 ms 175880 KB Output is correct
14 Correct 2407 ms 175888 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 0 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 10 ms 1492 KB Output is correct
21 Correct 344 ms 7252 KB Output is correct
22 Correct 6 ms 724 KB Output is correct
23 Correct 10 ms 1444 KB Output is correct
24 Correct 316 ms 7252 KB Output is correct
25 Correct 84 ms 7180 KB Output is correct
26 Correct 509 ms 7308 KB Output is correct
27 Correct 333 ms 7296 KB Output is correct
28 Correct 769 ms 18556 KB Output is correct
29 Correct 3393 ms 180184 KB Output is correct
30 Correct 821 ms 18536 KB Output is correct
31 Correct 3459 ms 180168 KB Output is correct
32 Correct 1160 ms 179124 KB Output is correct
33 Correct 3431 ms 178960 KB Output is correct
34 Correct 3112 ms 183752 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Incorrect 392 ms 5024 KB Output isn't correct
38 Halted 0 ms 0 KB -