Submission #980167

#	Time	Username	Problem	Language	Result	Execution time	Memory
980167		vjudge1	Closing Time (IOI23_closing)	C++17	21 / 100	1053 ms	18424 KiB

closing

#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>;using ii = pair<int,int>;using mii = map<int,int>;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
const int LOG = 13;
struct fenwick{
    vector<ll> ft;int n;
    fenwick(int kkk){n=kkk;ft.resize(n+2,0);}
    void update(int idx, ll val){for(; idx < n; idx += lsb(idx))ft[idx]+=val;}
    ll query(int idx){ll res = 0;for(;idx>0;idx-=lsb(idx))res+=ft[idx];return res;}
    ll query(int l, int r ){if(l>r)return 0;return query(r) - query(l-1);}
    int lwb(ll v){
        ll sum = 0;int pos=0;
        for(int i=LOG; i>=0; i--)
            if(pos + (1 << i) < n and sum + ft[pos + (1 << i)] < v){
                sum += ft[pos + (1 << i)];pos += (1 << i);
            }return pos + 1;
    }
};
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w){
    ll suf[n+1]{}, pre[n+1]{};
    fore(i,1,n)pre[i] = (i ? w[i-1] : 0) + (i ? pre[i-1] : 0);
    ffo(i,n-1)suf[i] = w[i] + suf[i+1];
    ll disx[n+1]{};
    for(int i = x-1; i >= 0; i--)disx[i] = disx[i+1] + w[i];
    ll disy[n+1]{} , ans = 0;
    for(int i = y+1; i <= n-1;i++)disy[i] = disy[i-1] + w[i-1];
    int tot = 0;
    vi ord;fo(i,x+1)ord.pb(disx[i]);fore(i,y,n)ord.pb(disy[i]);
    sort(all(ord)) ;
    // for(int v : ord) cout << v << " ";cout<<endl;
    for(int j = x; j <= n-1; j++ ){
        // cout << "Nuevo indice " << j << endl;
        ans+= pre[j] - pre[x];
        fenwick cnt(2*n+1), sum(2*n+1);
        for(int l=y;l>=0;l--){
            if(l>j)ans+=suf[l]- suf[y];
            else{
                if(l>x){
                    if(j>=l){
                        if(suf[l]-suf[y] > pre[l] - pre[x]){
                            ans -= pre[l] - pre[x];
                            ans+=suf[l]-suf[y];
                        }
                    }
                    else ans+= suf[l]-suf[y];
                }
                else{ans+=suf[l]-suf[y];if(l>=j)ans-=suf[l] - suf[x];}
            }
        }
        for(int i = max(y+1,j+1); i <= n-1; i++){
            // disy[i]
            // cout << disy[i] << " ";
            int pos = lower_bound(all(ord), disy[i])-ord.begin();
            // inserto esta, 1-indexado
            cnt.update(pos+1, +1);
            sum.update(pos+1, +disy[i]);
        }
        // cout<<endl;
        for(int l =0;l<=y;l++){
            if(ans <= k){
                int lb = 1, rb = cnt.query(1, 2*n);
                // cout << "Busqueda binaria " << endl;
                while(lb<=rb){
                    int mid = (lb+rb)/2;
                    // ahora quiero poner mid nuevos
                    // cout << lb << " " << rb << " " << mid << endl;
                    int pos = cnt.lwb(mid);
                    // cout << "Posicion del ultimo valor que debería poner" << endl;
                    // cout << pos << endl;
                    // cout << "Valor" << endl;
                    // cout << ord[pos-1] << endl;
                    ll con = sum.query(1, pos-1) + ((mid-cnt.query(1,pos-1))* ord[pos-1]);
                    // cout << "Lo que me cuesta" << endl;
                    // cout << con << endl;
                    if(con+ans <= k) lb = mid+1;
                    else rb = mid-1;
                }
                // cout << j << " " << l << " " << rb << endl; 
                tot = max(tot, j-x+1 + y-l+1 + rb + max(j-y, 0) + max(x-l, 0));
                // cout << j-x+1 + y-l+1 + rb + max(j-y, 0) + max(x-l, 0) << endl;
            }
            // cout << ans << " " << j << " " << l << " " << lb << " " << rb << endl;
            // for(int idx = 1; idx <= 2*n;idx++)cout << cnt.query(idx,idx) << " ";cout << endl;
            // for(int idx = 1; idx <= 2*n; idx ++ )cout << sum.query(idx,idx) << " "; cout << endl;
            // cout << endl << endl;
            if(l>j)ans-=suf[l]- suf[y];
            else{
                if(l>x){
                    if(j>=l){
                        if(suf[l]-suf[y] > pre[l] - pre[x]){
                            ans += pre[l] - pre[x];
                            ans -=suf[l]-suf[y];
                        }
                    }
                    else ans -= suf[l]-suf[y];
                }
                else{ans-=suf[l]-suf[y];if(l>=j)ans+=suf[l] - suf[x];}
            }
            // insertar disx[l]
            int pos = lower_bound(all(ord), disx[l])-ord.begin();
            // inserto esta, 1-indexado
            if(l <= x-1){
                cnt.update(pos+1, +1);
                sum.update(pos+1, +disx[l]);
            }
        }
    }
    return tot;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17