Submission #557948

#	Time	Username	Problem	Language	Result	Execution time	Memory
557948		new_acc	Akcija (COCI21_akcija)	C++14	110 / 110	1320 ms	46624 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e3+10;
const int SS=1<<12;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int seg[(SS<<1)+10],lazy[(SS<<1)+10],pop[N*N],akt[N][N],kt[N*N],pierw[N],n,wsk,wsk2,ff[N];
pair<int,int>t[N];
bitset<N>bi[N];
set<pair<pair<int,ll>,int> >s;
vi base;
void push(int v){
    lazy[v<<1]+=lazy[v],lazy[(v<<1)+1]+=lazy[v];
    seg[v<<1]+=lazy[v],seg[(v<<1)+1]+=lazy[v];
    lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        lazy[v]+=x,seg[v]+=x;
        return;
    }
    push(v);
    upd(a,b,x,p,(p+k)>>1,v<<1),upd(a,b,x,((p+k)>>1)+1,k,(v<<1)+1);
    seg[v]=min(seg[v<<1],seg[(v<<1)+1]);
}
int Query(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return INFi;
    if(p>=a and k<=b){
        base.push_back(v);
        return seg[v];
    }
    push(v);
    int wtf=Query(a,b,p,(p+k)>>1,v<<1);
    return min(wtf,Query(a,b,((p+k)>>1)+1,k,(v<<1)+1));
}
int Query2(int v){
    if(v>SS) return v-SS;
    push(v);
    if(seg[(v<<1)]<=0) return Query2(v<<1);
    else return Query2((v<<1)+1);
}
void clear(int v){
    lazy[v]=0;
    if(v>SS){
        seg[v]=v-SS;
        return;
    }
    clear(v<<1),clear((v<<1)+1);
    seg[v]=min(seg[(v<<1)],seg[(v<<1)+1]);
}
void cnt(int sid,int id){
    clear(1);
    for(int i=1;i<=n;i++){
        if(bi[pop[id]][i] and i<kt[id]) akt[sid][i]=1;
        else{
            if(bi[pop[id]][i] and i==kt[id]) akt[sid][i]=-1;
            else akt[sid][i]=akt[pop[id]][i];
        }
    }
    for(int i=1;i<=n;i++)
        if(akt[sid][i]==1) upd(t[i].se,n,-1);
    for(int i=1;i<=n;i++){
        if(akt[sid][i]!=0) continue;
        base.clear();
        if(akt[sid][i]==0 and Query(t[i].se,n)>0) upd(t[i].se,n,-1),bi[sid][i]=1;
        else{
            ff[i]=-1;
            for(auto u:base){
                if(seg[u]<=0){
                    ff[i]=Query2(u);
                    break;
                }
            }
        }
    }
    vector<pair<int,int> >deq;
    auto bs=[&](int pocz,int kon,int x){
        int sr,res=-1;
        while(pocz<=kon){
            sr=(pocz+kon)>>1;
            if(deq[sr].fi>=x) pocz=sr+1,res=deq[sr].se;
            else kon=sr-1;
        }
        return res;
    };
    for(int i=n;i>=1;i--){
        if(akt[sid][i]==1 or akt[sid][i]==-1) continue;
        if(bi[sid][i]) pierw[i]=bs(0,deq.size()-1,t[i].se);
        else{
            while(deq.size() and deq.back().fi<=ff[i]) deq.pop_back();
            deq.push_back({ff[i],i});
        }
    }
    ll a1=0;
    int a2=0;
    for(int i=1;i<=n;i++) if(akt[sid][i]==1 or bi[sid][i]) a1+=(ll)t[i].fi,a2++;
    cout<<a2<<" "<<a1<<"\n";
    for(int i=1;i<=n;i++){
        if(akt[sid][i]==1 or akt[sid][i]==-1 or !bi[sid][i]) continue;
        if(pierw[i]==-1) s.insert({{(a2-1)*(-1),a1-t[i].fi},++wsk});
        else s.insert({{a2*(-1),a1-(ll)t[i].fi+(ll)t[pierw[i]].fi},++wsk});
        pop[wsk]=sid,kt[wsk]=i;
    }
}
void solve(){
    int k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>t[i].fi>>t[i].se;
    sort(t+1,t+1+n,[](pair<int,int> a,pair<int,int> b){
        if(a.fi==b.fi) return a.se>b.se;
        return a.fi<b.fi;
    });
    wsk=1,wsk2=1;
    cnt(1,1);
    while(s.size()){
        auto it=s.begin();
        pair<pair<int,ll>,int> curr=*it;
        s.erase(it); 
        ++wsk2;
        if(wsk2==k+1) return;
        cnt(wsk2,curr.se);
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 30 / 30
• Subtask 6: 20 / 20