oj.uz

Submission #929073

# Submission time Handle Problem Language Result Execution time Memory
929073 2024-02-17T16:21:48 Z GrindMachine Teams (IOI15_teams) C++17
77 / 100
 4000 ms 140828 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;

    auto odp = dp;

    rep1(i,m-1){
        while(!leave[i].empty()){
            ll j = leave[i].back();
            leave[i].pop_back();
            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);
            }
        }

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

    // debug(dp);
    // debug(odp);

    assert(dp == odp);

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

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:194:26: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
  194 |             if(!st.count(j)) conts;
      |                          ^
teams.cpp:195:22: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
  195 |             st.erase(j);
      |                      ^
teams.cpp:197:38: warning: conversion from 'll' {aka 'long long int'} to 'std::set<int>::key_type' {aka 'int'} may change value [-Wconversion]
  197 |             auto it = st.upper_bound(j);
      |                                      ^

Subtask #1
21.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 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 0 ms 344 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 27592 KB Output is correct
2 Correct 72 ms 27592 KB Output is correct
3 Correct 67 ms 27644 KB Output is correct
4 Correct 67 ms 27592 KB Output is correct
5 Correct 50 ms 26780 KB Output is correct
6 Correct 43 ms 26976 KB Output is correct
7 Correct 50 ms 26928 KB Output is correct
8 Correct 50 ms 26968 KB Output is correct
9 Correct 40 ms 47812 KB Output is correct
10 Correct 34 ms 33220 KB Output is correct
11 Correct 34 ms 33228 KB Output is correct
12 Correct 36 ms 33476 KB Output is correct
13 Correct 42 ms 33220 KB Output is correct
14 Correct 54 ms 41260 KB Output is correct
15 Correct 62 ms 27588 KB Output is correct
16 Correct 62 ms 27468 KB Output is correct
17 Correct 38 ms 26816 KB Output is correct
18 Correct 39 ms 26976 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2430 ms 27508 KB Output is correct
2 Correct 2190 ms 27588 KB Output is correct
3 Correct 186 ms 28372 KB Output is correct
4 Correct 68 ms 27588 KB Output is correct
5 Correct 2763 ms 26820 KB Output is correct
6 Correct 2261 ms 26832 KB Output is correct
7 Correct 2766 ms 26820 KB Output is correct
8 Correct 2293 ms 26820 KB Output is correct
9 Correct 40 ms 48052 KB Output is correct
10 Correct 36 ms 33224 KB Output is correct
11 Correct 62 ms 33220 KB Output is correct
12 Correct 675 ms 33300 KB Output is correct
13 Correct 257 ms 33356 KB Output is correct
14 Correct 211 ms 30920 KB Output is correct
15 Correct 167 ms 27592 KB Output is correct
16 Correct 162 ms 27588 KB Output is correct
17 Correct 194 ms 27068 KB Output is correct
18 Correct 154 ms 28236 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 140828 KB Time limit exceeded
2 Halted 0 ms 0 KB -