oj.uz

Submission #557881

# Submission time Handle Problem Language Result Execution time Memory
557881 2022-05-06T08:57:04 Z new_acc Akcija (COCI21_akcija) C++14
30 / 110
 72 ms 8924 KB 
#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;
pair<int,int>t[N];
bitset<N>bi[N];
set<pair<pair<int,ll>,int> >s;
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) return seg[v];
    push(v);
    return min(Query(a,b,p,(p+k)>>1,v<<1),Query(a,b,((p+k)>>1)+1,k,(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 and Query(t[i].se,n)>0) upd(t[i].se,n,-1),bi[sid][i]=1;
    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) kon=sr-1,res=deq[sr].se;
            else pocz=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<=t[i].se) deq.pop_back();
            deq.push_back({t[i].se,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);
    s.insert({{0,0},1});
    wsk=1,wsk2=1;
    cnt(1,1);
    s.erase({{0,0},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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 584 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 364 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8924 KB Output is correct
2 Incorrect 72 ms 8760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 584 KB Output is correct
18 Correct 3 ms 596 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 2 ms 364 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Incorrect 2 ms 596 KB Output isn't correct
28 Halted 0 ms 0 KB -