oj.uz

Submission #929068

# Submission time Handle Problem Language Result Execution time Memory
929068 2024-02-17T16:10:22 Z GrindMachine Teams (IOI15_teams) C++17
13 / 100
 765 ms 254180 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, 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 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 492 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 1 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 67 ms 27592 KB Output is correct
2 Correct 66 ms 27760 KB Output is correct
3 Correct 66 ms 27592 KB Output is correct
4 Correct 74 ms 27608 KB Output is correct
5 Correct 39 ms 26824 KB Output is correct
6 Correct 38 ms 26820 KB Output is correct
7 Correct 39 ms 26948 KB Output is correct
8 Correct 39 ms 26832 KB Output is correct
9 Correct 41 ms 47812 KB Output is correct
10 Correct 35 ms 33480 KB Output is correct
11 Correct 34 ms 33064 KB Output is correct
12 Correct 36 ms 33272 KB Output is correct
13 Correct 43 ms 33292 KB Output is correct
14 Correct 53 ms 41420 KB Output is correct
15 Correct 62 ms 27540 KB Output is correct
16 Correct 63 ms 27500 KB Output is correct
17 Correct 39 ms 26824 KB Output is correct
18 Correct 39 ms 26820 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 27708 KB Output is correct
2 Correct 113 ms 27680 KB Output is correct
3 Correct 179 ms 28132 KB Output is correct
4 Correct 68 ms 27692 KB Output is correct
5 Correct 157 ms 26820 KB Output is correct
6 Correct 136 ms 26792 KB Output is correct
7 Correct 150 ms 26820 KB Output is correct
8 Correct 138 ms 26832 KB Output is correct
9 Correct 41 ms 47812 KB Output is correct
10 Correct 37 ms 33220 KB Output is correct
11 Correct 45 ms 33224 KB Output is correct
12 Correct 104 ms 33312 KB Output is correct
13 Incorrect 144 ms 33604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 140764 KB Output is correct
2 Correct 448 ms 148112 KB Output is correct
3 Correct 765 ms 149608 KB Output is correct
4 Correct 366 ms 147768 KB Output is correct
5 Correct 487 ms 142024 KB Output is correct
6 Correct 456 ms 141892 KB Output is correct
7 Correct 488 ms 142000 KB Output is correct
8 Correct 458 ms 142008 KB Output is correct
9 Correct 223 ms 254180 KB Output is correct
10 Correct 177 ms 175640 KB Output is correct
11 Correct 249 ms 176484 KB Output is correct
12 Correct 356 ms 180032 KB Output is correct
13 Incorrect 581 ms 177608 KB Output isn't correct
14 Halted 0 ms 0 KB -