oj.uz

Submission #1029625

# Submission time Handle Problem Language Result Execution time Memory
1029625 2024-07-21T06:26:03 Z hotboy2703 Comparing Plants (IOI20_plants) C++17
44 / 100
 353 ms 22928 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];
        ll lazy[MAXN*4];
        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){
//                cout<<"UPD2 "<<l<<' '<<r<<endl;
                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){
//                cout<<"BRUH "<<i<<endl;
                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 sus(ll i,ll id=1,ll l=0,ll r=n-1){
            if (i > r || l > i)return INF+1;
            if (l == r)return tree[id].fi;
            lz(id);
            ll mid = (l + r) >> 1;
            return min(sus(i,id<<1,l,mid),sus(i,id<<1|1,mid+1,r));
        }
    }
    ll h[MAXN];
    ll label;
    bool in[MAXN];
    vector <ll> all;
    void solve(ll x){
//        assert(in[x] == 0);
//        in[x] = 1;
        ll l = x-k+1,r=x-1;
//        cout<<x<<' '<<l<<' '<<r<<endl;
        ll tmp;
        while ((tmp=seg::get(l,r)) != n+1){
            solve(tmp);
        }
        while ((tmp=seg::get(l+n,r+n)) != n+1){
//            cout<<x<<' '<<tmp<<endl;
            solve(tmp);
        }

        all.push_back(x);
        seg::del(x);
        h[x] = --label;
        seg::update(l,r);
        seg::update(l+n,r+n);
    }
}
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){
        }
        all.clear();
    }
//    for (ll i = 0;i < n;i ++)cout<<h[i]<<' ';
//    cout<<'\n';
//    for (ll i = 0;i < n;i ++){
//        ll cnt = 0;
//        for (ll j = 1;j < k;j ++){
//            if (h[(i+j)%n] > h[i])cnt++;
//        }
//        assert(cnt==r[i]);
//    }
}
int compare_plants(int x, int y){
     using namespace trung;
    return (h[x] > h[y] ? 1 : -1);
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:124:19: warning: unused variable 'x' [-Wunused-variable]
  124 |         for (auto x:all){
      |                   ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.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 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 43 ms 5460 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 44 ms 5392 KB Output is correct
11 Correct 35 ms 5316 KB Output is correct
12 Correct 34 ms 5444 KB Output is correct
13 Correct 41 ms 5396 KB Output is correct

Subtask #3
13.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 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 43 ms 5460 KB Output is correct
8 Correct 1 ms 456 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 44 ms 5392 KB Output is correct
11 Correct 35 ms 5316 KB Output is correct
12 Correct 34 ms 5444 KB Output is correct
13 Correct 41 ms 5396 KB Output is correct
14 Correct 59 ms 7084 KB Output is correct
15 Correct 340 ms 22104 KB Output is correct
16 Correct 59 ms 7204 KB Output is correct
17 Correct 324 ms 22096 KB Output is correct
18 Correct 207 ms 21844 KB Output is correct
19 Correct 178 ms 22008 KB Output is correct
20 Correct 353 ms 22108 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 36 ms 4888 KB Output is correct
4 Correct 181 ms 22928 KB Output is correct
5 Correct 220 ms 22024 KB Output is correct
6 Correct 270 ms 21872 KB Output is correct
7 Correct 300 ms 21924 KB Output is correct
8 Correct 309 ms 22060 KB Output is correct
9 Correct 160 ms 21840 KB Output is correct
10 Correct 164 ms 21352 KB Output is correct
11 Correct 130 ms 21584 KB Output is correct
12 Correct 155 ms 21672 KB Output is correct
13 Correct 196 ms 21732 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -