oj.uz

Submission #1029591

# Submission time Handle Problem Language Result Execution time Memory
1029591 2024-07-21T05:02:24 Z hotboy2703 Comparing Plants (IOI20_plants) C++17
0 / 100
 4000 ms 1051200 KB 
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL<<(i))
namespace trung{
    const ll MAXN = 2e5+100;
    const ll INF = 1e9+7;
    ll n,k;
    vector <int> val;
    namespace seg{
        pll tree[MAXN*4+100];
        ll lazy[MAXN*4+100];
        pll combine(pll x,pll y){
            if (x.fi > y.fi)return y;
            else return x;
        }
        void build(ll id=1,ll l=0,ll r=n-1){
            if (l==r){tree[id] = MP(val[l],l);}
            else{
                ll mid = (l + r) >> 1;
                build(id<<1,l,mid);
                build(id<<1|1,mid+1,r);
                tree[id] = combine(tree[id<<1],tree[id<<1|1]);
            }
        }
        void push(ll id,ll x){
            tree[id].fi+=x;
            lazy[id]+=x;
        }
        void lz(ll id){
            push(id<<1,lazy[id]);
            push(id<<1|1,lazy[id]);
            lazy[id] = 0;
        }
        void update(ll l1,ll r1,ll id=1,ll l=0,ll r=n-1){
//            if (id==1)cout<<"UPD "<<l1<<' '<<r1<<endl;
            if (l1 > r || l > r1 || l1 > r1)return;
            if (l1 <= l && r <= r1){
                push(id,-1);
                return;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            update(l1,r1,id<<1,l,mid);
            update(l1,r1,id<<1|1,mid+1,r);
            tree[id] = combine(tree[id<<1],tree[id<<1|1]);
        }
        void del(ll i,ll id=1,ll l=0,ll r=n-1){
            if (l > i || i > r)return;
            if (l==r){
                tree[id].fi = INF;
                return;
            }
            lz(id);
            ll mid = (l + r) >> 1;
            del(i,id<<1,l,mid);
            del(i,id<<1|1,mid+1,r);
            tree[id] = combine(tree[id<<1],tree[id<<1|1]);
        }
        ll get(ll l1,ll r1,ll id=1,ll l=0,ll r=n-1){
            if (l1 > r || l > r1 || l1 > r1)return n+1;
            if (tree[id].fi!=0)return n+1;
            if (l1 <= l && r <= r1)return tree[id].se;
            lz(id);
            ll mid = (l + r) >> 1;
            ll res = get(l1,r1,id<<1,l,mid);
            if (res==n+1)res = get(l1,r1,id<<1|1,mid+1,r);
            return res;
        }
    }
    ll h[MAXN];
    ll label;
    vector <ll> all;
    void solve(ll x){
        ll l = x-k+1,r=x-1;
//        cout<<x<<' '<<l<<' '<<r<<endl;
        ll tmp;
        while ((tmp=seg::get(l+n,r+n)) != n+1){
            solve(tmp);
        }
        while ((tmp=seg::get(l,r)) != n+1){
            solve(tmp);
        }
        all.push_back(x);
    }
}
void init(int K, std::vector<int> r){
    using namespace trung;
    val = r;
    n=sz(r);
    k=K;
    seg::build();
//    cout<<"OK"<<endl;
    ll cur;
    label = n;
    while ((cur=seg::get(0,n-1)) != n+1){
//        cout<<"CUR "<<cur<<endl;
        solve(cur);
        for (auto x:all){
            h[x] = --label;
            ll l = x-k+1,r=x-1;
            seg::update(l,r);
            seg::update(l+n,r+n);
            seg::del(x);
        }
        all.clear();
    }
}
int compare_plants(int x, int y){
     using namespace trung;
    return (h[x] > h[y] ? 1 : -1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 4120 ms 1051200 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 4128 ms 1050988 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 4128 ms 1050988 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 4110 ms 1051004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 4075 ms 1051004 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 4116 ms 1051048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 4120 ms 1051200 KB Time limit exceeded
5 Halted 0 ms 0 KB -