oj.uz

답안 #929074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
929074 2024-02-17T16:22:25 Z GrindMachine 팀들 (IOI15_teams) C++17
100 / 100
 887 ms 249272 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

# 결과 실행 시간 메모리 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 344 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 0 ms 348 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 0 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 0 ms 348 KB Output is correct
21 Correct 0 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 344 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 27756 KB Output is correct
2 Correct 66 ms 27992 KB Output is correct
3 Correct 65 ms 27736 KB Output is correct
4 Correct 67 ms 27592 KB Output is correct
5 Correct 38 ms 27024 KB Output is correct
6 Correct 38 ms 26816 KB Output is correct
7 Correct 39 ms 26840 KB Output is correct
8 Correct 42 ms 26820 KB Output is correct
9 Correct 39 ms 47816 KB Output is correct
10 Correct 34 ms 33236 KB Output is correct
11 Correct 35 ms 33220 KB Output is correct
12 Correct 36 ms 33480 KB Output is correct
13 Correct 46 ms 33224 KB Output is correct
14 Correct 50 ms 41360 KB Output is correct
15 Correct 61 ms 27684 KB Output is correct
16 Correct 61 ms 27476 KB Output is correct
17 Correct 38 ms 27056 KB Output is correct
18 Correct 42 ms 26888 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 27616 KB Output is correct
2 Correct 112 ms 27480 KB Output is correct
3 Correct 148 ms 28208 KB Output is correct
4 Correct 67 ms 27592 KB Output is correct
5 Correct 147 ms 26960 KB Output is correct
6 Correct 128 ms 26824 KB Output is correct
7 Correct 142 ms 26968 KB Output is correct
8 Correct 135 ms 26824 KB Output is correct
9 Correct 39 ms 47812 KB Output is correct
10 Correct 36 ms 33096 KB Output is correct
11 Correct 51 ms 33224 KB Output is correct
12 Correct 102 ms 33476 KB Output is correct
13 Correct 139 ms 33224 KB Output is correct
14 Correct 204 ms 30920 KB Output is correct
15 Correct 109 ms 27592 KB Output is correct
16 Correct 119 ms 27676 KB Output is correct
17 Correct 93 ms 27068 KB Output is correct
18 Correct 78 ms 28232 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 448 ms 140780 KB Output is correct
2 Correct 446 ms 140728 KB Output is correct
3 Correct 714 ms 141424 KB Output is correct
4 Correct 344 ms 140660 KB Output is correct
5 Correct 471 ms 137336 KB Output is correct
6 Correct 446 ms 137156 KB Output is correct
7 Correct 473 ms 137404 KB Output is correct
8 Correct 448 ms 137404 KB Output is correct
9 Correct 209 ms 249272 KB Output is correct
10 Correct 174 ms 172476 KB Output is correct
11 Correct 228 ms 172732 KB Output is correct
12 Correct 350 ms 175472 KB Output is correct
13 Correct 598 ms 171712 KB Output is correct
14 Correct 887 ms 165940 KB Output is correct
15 Correct 414 ms 147640 KB Output is correct
16 Correct 408 ms 147388 KB Output is correct
17 Correct 311 ms 144028 KB Output is correct
18 Correct 311 ms 148340 KB Output is correct