Submission #1025539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025539		boyliguanhan	Teams (IOI15_teams)	C++17	100 / 100	2471 ms	238008 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(3)
struct persissegtree{
    int vl[1<<24]{},lc[1<<24]{},rc[1<<24]{},CC=0,N_;
    void init(int N){
        N_=N;
    }
    int NN(int i){
        vl[++CC]=vl[i]+1;
        return CC;
    }
    int NN(int l,int r){
        vl[++CC]=vl[l]+vl[r];
        lc[CC]=l,rc[CC]=r;
        return CC;
    }
    int updated(int i,int l,int r,int p){
        if(l==r)return NN(i);
        if(l+r>>1<p)return NN(lc[i],
            updated(rc[i],l+r+2>>1,r,p));
        return NN(updated(lc[i],l,l+r>>1,p),rc[i]);
    }
    int qwerwry(int i,int l,int r,int ll,int rr){
        if(!i) return 0;
        if(l>rr||ll>r) return 0;
        if(ll<=l&&r<=rr) return vl[i];
        return qwerwry(lc[i],l,l+r>>1,ll,rr)+
            qwerwry(rc[i],l+r+2>>1,r,ll,rr);
    }
    int adto(int node,int ind){
        return updated(node,1,N_,ind);
    }
    int querybef(int node,int ind){
        return qwerwry(node,1,N_,1,ind);
    }
} APST;
int N_;
vector<pair<int,int>>stuff,stuff2;
vector<int>PWB[500100],lolwhy{0};
void init(int N, int A[], int B[]) {
    APST.init(N);
    N_=N;
    for(int i=0;i<N;i++)
        stuff.push_back({A[i],B[i]}),
        PWB[N-A[i]+1].push_back(B[i]);
    sort(stuff.begin(),stuff.end());
    int lstnode=0;
    for(int i=1;i<=N;i++){
        for(auto y:PWB[i])
            lstnode=APST.adto(lstnode,y);
        lolwhy.push_back(lstnode);
    }
}
int dobig(map<int,int>mp){
    int pos=0;
    priority_queue<int>pq;
    for(auto[i,x]:mp){
        while(pos<N_&&stuff[pos].first<=i)
            pq.push(-stuff[pos++].second);
        while(pq.size()&&-pq.top()<i)
            pq.pop();
        while(x--){
            if(pq.empty())return 0;
            pq.pop();
        }
    }
    return 1;
}
int queryallbet(int l,int r){
    return APST.querybef(lolwhy[N_-l+1],r-1);
}
int REV[1010];
int dosmall(map<int,int>REQ){
    vector<int>pref{0},dp;
    int CC=0;
    for(auto[x,y]:REQ) REV[++CC]=x,
        pref.push_back(pref.back()+y);
    pref.push_back(pref.back());
    REV[0]=0;
    REV[++CC]=N_+1;
    dp.resize(pref.size());
    int orig=queryallbet(REV[0]+1,REV[CC])-pref.back();
    for(int i=1;i<=CC;i++){
        dp[i]=dp[i-1];
        for(int j=0;j<i;j++){
            dp[i]=min(dp[i],dp[j]+pref[i-1]-pref[j]-queryallbet(REV[j]+1,REV[i]));
        }
        if(-dp[i]>orig)
            return 0;
    }
    return 1;
}
int can(int M, int K[]) {
    map<int,int>REQ;
    int SM=0;
    for(int i=0;i<M;i++) SM+=K[i],
        REQ[K[i]]+=K[i],SM=min(N_+1,SM);
    if(SM>N_) return 0;
    if(M>500) return dobig(REQ);
    return dosmall(REQ);
}

Compilation message (stderr)

teams.cpp: In member function 'int persissegtree::updated(int, int, int, int)':
teams.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         if(l+r>>1<p)return NN(lc[i],
      |            ~^~
teams.cpp:22:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             updated(rc[i],l+r+2>>1,r,p));
      |                           ~~~^~
teams.cpp:23:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         return NN(updated(lc[i],l,l+r>>1,p),rc[i]);
      |                                   ~^~
teams.cpp: In member function 'int persissegtree::qwerwry(int, int, int, int, int)':
teams.cpp:29:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         return qwerwry(lc[i],l,l+r>>1,ll,rr)+
      |                                ~^~
teams.cpp:30:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |             qwerwry(rc[i],l+r+2>>1,r,ll,rr);
      |                           ~~~^~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23