oj.uz

Submission #929071

# Submission time Handle Problem Language Result Execution time Memory
929071 2024-02-17T16:12:50 Z GrindMachine Teams (IOI15_teams) C++17
13 / 100
 713 ms 249464 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

*/

const int MOD = 1e9 + 7;
const int N = 5e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "teams.h"

struct wavelet_tree{
    struct node{
        node *l, *r;
        vector<int> b;
    };
 
    node* root;
    int siz;
 
    wavelet_tree(){
 
    }
 
    node* build(vector<int> &a, vector<int> inds, int l, int r){
        if(l > r) return NULL;
        int mid = (l+r) >> 1;
        vector<int> b(sz(inds)+1);
 
        vector<int> la,ra;
        rep(i,sz(inds)){
            int x = a[inds[i]];
            b[i+1] = b[i]+(x <= mid);
            if(x <= mid){
                la.pb(inds[i]);
            }
            else{
                ra.pb(inds[i]);
            }
        }
 
        node* curr = new node();
        curr->b = b;
 
        if(l != r){         
            curr->l = build(a,la,l,mid);
            curr->r = build(a,ra,mid+1,r);
        }
 
        return curr;
    }
 
    void build(vector<int> &a, int mx_siz){
        siz = mx_siz;
        vector<int> inds;
        rep(i,sz(a)) inds.pb(i);
        root = build(a,inds,0,siz);
    }

    int get_cnt(node* u, int lx, int rx, int l, int r, int vl, int vr){
        if(!u) return 0;
        if(l > r) return 0;
        if(lx > vr or rx < vl) return 0;
        if(lx >= vl and rx <= vr) return r-l+1;

        int mid = (lx+rx) >> 1;

        auto &b = u->b;

        int res = 0;
        res += get_cnt(u->l,lx,mid,b[l-1]+1,b[r],vl,vr);
        res += get_cnt(u->r,mid+1,rx,l-b[l-1],r-b[r],vl,vr);
        
        return res;
    }

    int get_cnt(int l, int r, int vl, int vr){
        return get_cnt(root,0,siz,l+1,r+1,vl,vr);
    }
};

int n;
vector<pii> a;
wavelet_tree wt;
vector<int> lb;

void init(int n_, int A[], int B[]) {
    n = n_;
    rep(i,n) a.pb({A[i],B[i]});
    sort(all(a));

    lb = vector<int>(n+5,n);
    rep(i,n) amin(lb[a[i].ff],i);
    rev(i,n,0) amin(lb[i],lb[i+1]);

    vector<int> b;
    rep(i,n) b.pb(a[i].ss);

    wt.build(b,n+1);
}

int can(int m, int K[]) {
    int sum = 0;
    rep(i,m){
        sum += K[i];
        if(sum > n){
            return 0;
        }
    }

    sort(K,K+m);
    vector<pii> c;
    c.pb({K[0],K[0]});
    rep1(i,m-1){
        if(K[i] == K[i-1]){
            c.back().ss += K[i];
        }
        else{
            c.pb({K[i],K[i]});
        }
    }

    auto get = [&](int mnl, int mxl, int mnr){
        return wt.get_cnt(lb[mnl],lb[mxl+1]-1,mnr,n);
    };

    c.insert(c.begin(),{0,0});
    m = sz(c);
    set<int> st;
    st.insert(0);

    vector<int> leave[m];

    vector<int> dp(m,inf1);
    dp[0] = 0;

    rep1(i,m-1){
        trav(j,leave[i]){
            if(!st.count(j)) conts;
            st.erase(j);
            auto it = st.upper_bound(j);
            if(it != st.end() and it != st.begin()){
                int x = *prev(it), y = *it;
                int val = dp[y]-dp[x];
                int lo = i, hi = m-1;
                int pos = -1;

                while(lo <= hi){
                    int mid = (lo+hi) >> 1;
                    if(val >= get(c[x].ff+1,c[y].ff,c[mid].ff)){
                        pos = mid;
                        hi = mid-1;
                    }
                    else{
                        lo = mid+1;
                    }
                }

                if(pos != -1){
                    leave[pos].pb(y);
                }
            }
        }

        {
            int j = *st.rbegin();
            dp[i] = dp[j]+get(c[j].ff+1,c[i].ff,c[i].ff)-c[i].ss;
        }

        st.insert(i);
        auto it = st.find(i);

        {
            int x = *prev(it), y = *it;
            int val = dp[y]-dp[x];
            int lo = i+1, hi = m-1;
            int pos = -1;

            while(lo <= hi){
                int mid = (lo+hi) >> 1;
                if(val >= get(c[x].ff+1,c[y].ff,c[mid].ff)){
                    pos = mid;
                    hi = mid-1;
                }
                else{
                    lo = mid+1;
                }
            }

            if(pos != -1){
                leave[pos].pb(y);
            }
        }

        // dp[i] = inf1;

        // rep(j,i){
        //     amin(dp[i],dp[j]+get(c[j].ff+1,c[i].ff,c[i].ff));
        // }
        // dp[i] -= c[i].ss;
    }

    int mn = *min_element(all(dp));
    return mn >= 0;
}

Subtask #1
0 / 21.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 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 27592 KB Output is correct
2 Correct 65 ms 27592 KB Output is correct
3 Correct 73 ms 27568 KB Output is correct
4 Correct 69 ms 27592 KB Output is correct
5 Correct 39 ms 26824 KB Output is correct
6 Correct 39 ms 26824 KB Output is correct
7 Correct 39 ms 26824 KB Output is correct
8 Correct 39 ms 26824 KB Output is correct
9 Correct 44 ms 48292 KB Output is correct
10 Correct 35 ms 33224 KB Output is correct
11 Correct 34 ms 33232 KB Output is correct
12 Correct 36 ms 33484 KB Output is correct
13 Correct 44 ms 33220 KB Output is correct
14 Correct 55 ms 41376 KB Output is correct
15 Correct 62 ms 27520 KB Output is correct
16 Correct 62 ms 27576 KB Output is correct
17 Correct 39 ms 26824 KB Output is correct
18 Correct 39 ms 26892 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 27656 KB Output is correct
2 Correct 126 ms 27592 KB Output is correct
3 Correct 150 ms 28100 KB Output is correct
4 Correct 68 ms 27588 KB Output is correct
5 Correct 150 ms 26788 KB Output is correct
6 Correct 130 ms 26908 KB Output is correct
7 Correct 139 ms 26924 KB Output is correct
8 Correct 139 ms 26824 KB Output is correct
9 Correct 41 ms 47680 KB Output is correct
10 Correct 37 ms 33132 KB Output is correct
11 Correct 48 ms 33480 KB Output is correct
12 Correct 116 ms 33476 KB Output is correct
13 Incorrect 137 ms 33352 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 141068 KB Output is correct
2 Correct 445 ms 141240 KB Output is correct
3 Correct 713 ms 141300 KB Output is correct
4 Correct 352 ms 140596 KB Output is correct
5 Correct 466 ms 137404 KB Output is correct
6 Correct 449 ms 137916 KB Output is correct
7 Correct 466 ms 137200 KB Output is correct
8 Correct 452 ms 137272 KB Output is correct
9 Correct 205 ms 249464 KB Output is correct
10 Correct 185 ms 172632 KB Output is correct
11 Correct 249 ms 172448 KB Output is correct
12 Correct 352 ms 175544 KB Output is correct
13 Incorrect 571 ms 171944 KB Output isn't correct
14 Halted 0 ms 0 KB -