oj.uz

Submission #640515

# Submission time Handle Problem Language Result Execution time Memory
640515 2022-09-14T19:31:37 Z lis05st Comparing Plants (IOI20_plants) C++17
5 / 100
 549 ms 74196 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;
    }
}

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;
    for(int step=n;step>=1;){
        //for(int i=0;i<n;i++){
        //    int e=get(1,0,3*n-1,i,i,0).first;
        //    if(e>=100)cout<<"x ";
        //    else cout<<e<<" ";
        //}cout<<"\n";
        auto[val,pos]=get(1,0,3*n-1,L,R);
        //cout<<"step: "<<step<<"\n";
        //cout<<val<<":"<<pos<<" "<<pos%n<<endl;
        vector<int>vec2;
        vec2.push_back(pos);
        while(get(1,0,3*n-1,pos-k+1,pos-1).first==0){
            auto [val2,pos2]=get(1,0,3*n-1,pos-k+1,pos-1);
            pos=pos2;
            vec2.push_back(pos);
        }
        reverse(vec2.begin(),vec2.end());
        for(auto e:vec2){
            //cout<<"GOOD"<<endl;
            h[pos%n]=step--;
            add(pos-k+1,pos-1,-1);
            add(pos,pos,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
    }
}*/

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:147:18: warning: unused variable 'e' [-Wunused-variable]
  147 |         for(auto e:vec2){
      |                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 50 ms 3148 KB Output is correct
7 Correct 71 ms 5936 KB Output is correct
8 Correct 537 ms 74072 KB Output is correct
9 Correct 534 ms 74196 KB Output is correct
10 Correct 543 ms 74168 KB Output is correct
11 Correct 549 ms 74196 KB Output is correct
12 Correct 507 ms 74176 KB Output is correct
13 Correct 531 ms 74104 KB Output is correct
14 Correct 522 ms 74168 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 0 ms 316 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 #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 316 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 #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 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 316 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 50 ms 3148 KB Output is correct
7 Correct 71 ms 5936 KB Output is correct
8 Correct 537 ms 74072 KB Output is correct
9 Correct 534 ms 74196 KB Output is correct
10 Correct 543 ms 74168 KB Output is correct
11 Correct 549 ms 74196 KB Output is correct
12 Correct 507 ms 74176 KB Output is correct
13 Correct 531 ms 74104 KB Output is correct
14 Correct 522 ms 74168 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 316 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Halted 0 ms 0 KB -