oj.uz

Submission #641768

# Submission time Handle Problem Language Result Execution time Memory
641768 2022-09-17T15:04:46 Z lis05st Comparing Plants (IOI20_plants) C++17
32 / 100
 2680 ms 153880 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()==2*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=2*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<2*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<2*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()==2*n)break;
      |            ~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 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 Correct 0 ms 596 KB Output is correct
6 Correct 143 ms 3380 KB Output is correct
7 Correct 458 ms 14744 KB Output is correct
8 Correct 2032 ms 143520 KB Output is correct
9 Correct 2153 ms 143540 KB Output is correct
10 Correct 1855 ms 143628 KB Output is correct
11 Correct 1615 ms 143544 KB Output is correct
12 Correct 1528 ms 143596 KB Output is correct
13 Correct 768 ms 143528 KB Output is correct
14 Correct 1732 ms 143652 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 7 ms 1364 KB Output is correct
7 Correct 208 ms 6416 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct
10 Correct 227 ms 6404 KB Output is correct
11 Correct 91 ms 6240 KB Output is correct
12 Correct 276 ms 6544 KB Output is correct
13 Correct 213 ms 6464 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 7 ms 1364 KB Output is correct
7 Correct 208 ms 6416 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 8 ms 1372 KB Output is correct
10 Correct 227 ms 6404 KB Output is correct
11 Correct 91 ms 6240 KB Output is correct
12 Correct 276 ms 6544 KB Output is correct
13 Correct 213 ms 6464 KB Output is correct
14 Correct 388 ms 15172 KB Output is correct
15 Correct 2680 ms 146388 KB Output is correct
16 Correct 397 ms 17392 KB Output is correct
17 Correct 2676 ms 150124 KB Output is correct
18 Correct 1008 ms 148656 KB Output is correct
19 Correct 2327 ms 149292 KB Output is correct
20 Correct 2426 ms 153880 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 215 ms 4612 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 644 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 1 ms 596 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Incorrect 5 ms 1236 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 596 KB Output is correct
2 Correct 0 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 Correct 0 ms 596 KB Output is correct
6 Correct 143 ms 3380 KB Output is correct
7 Correct 458 ms 14744 KB Output is correct
8 Correct 2032 ms 143520 KB Output is correct
9 Correct 2153 ms 143540 KB Output is correct
10 Correct 1855 ms 143628 KB Output is correct
11 Correct 1615 ms 143544 KB Output is correct
12 Correct 1528 ms 143596 KB Output is correct
13 Correct 768 ms 143528 KB Output is correct
14 Correct 1732 ms 143652 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 0 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 2 ms 724 KB Output is correct
20 Correct 7 ms 1364 KB Output is correct
21 Correct 208 ms 6416 KB Output is correct
22 Correct 3 ms 724 KB Output is correct
23 Correct 8 ms 1372 KB Output is correct
24 Correct 227 ms 6404 KB Output is correct
25 Correct 91 ms 6240 KB Output is correct
26 Correct 276 ms 6544 KB Output is correct
27 Correct 213 ms 6464 KB Output is correct
28 Correct 388 ms 15172 KB Output is correct
29 Correct 2680 ms 146388 KB Output is correct
30 Correct 397 ms 17392 KB Output is correct
31 Correct 2676 ms 150124 KB Output is correct
32 Correct 1008 ms 148656 KB Output is correct
33 Correct 2327 ms 149292 KB Output is correct
34 Correct 2426 ms 153880 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Incorrect 215 ms 4612 KB Output isn't correct
38 Halted 0 ms 0 KB -