oj.uz

Submission #1029610

# Submission time Handle Problem Language Result Execution time Memory
1029610 2024-07-21T05:53:49 Z hotboy2703 Comparing Plants (IOI20_plants) C++17
44 / 100
 272 ms 23244 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+n,r+n)) != n+1){
//            cout<<x<<' '<<tmp<<endl;
            solve(tmp);
        }
        while ((tmp=seg::get(l,r)) != n+1){
            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:123:19: warning: unused variable 'x' [-Wunused-variable]
  123 |         for (auto x:all){
      |                   ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 1 ms 2396 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 2396 KB Output is correct
3 Correct 0 ms 2396 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 600 KB Output is correct
7 Correct 35 ms 7264 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 35 ms 5636 KB Output is correct
11 Correct 33 ms 5468 KB Output is correct
12 Correct 34 ms 5716 KB Output is correct
13 Correct 35 ms 5460 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 2396 KB Output is correct
3 Correct 0 ms 2396 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 600 KB Output is correct
7 Correct 35 ms 7264 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 35 ms 5636 KB Output is correct
11 Correct 33 ms 5468 KB Output is correct
12 Correct 34 ms 5716 KB Output is correct
13 Correct 35 ms 5460 KB Output is correct
14 Correct 51 ms 7476 KB Output is correct
15 Correct 272 ms 22612 KB Output is correct
16 Correct 49 ms 8788 KB Output is correct
17 Correct 246 ms 22760 KB Output is correct
18 Correct 159 ms 22128 KB Output is correct
19 Correct 153 ms 22616 KB Output is correct
20 Correct 252 ms 22652 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 46 ms 5048 KB Output is correct
4 Correct 134 ms 23244 KB Output is correct
5 Correct 153 ms 22356 KB Output is correct
6 Correct 207 ms 22360 KB Output is correct
7 Correct 220 ms 22360 KB Output is correct
8 Correct 235 ms 22612 KB Output is correct
9 Correct 158 ms 22084 KB Output is correct
10 Correct 152 ms 22004 KB Output is correct
11 Correct 128 ms 21844 KB Output is correct
12 Correct 137 ms 22140 KB Output is correct
13 Correct 159 ms 21920 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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