Submission #197913

#	Time	Username	Problem	Language	Result	Execution time	Memory
197913		mhy908	Teams (IOI15_teams)	C++14	100 / 100	3396 ms	337680 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
struct NODE{
    int val;
    NODE *l, *r;
    NODE(int _val, NODE *_l=nullptr, NODE *_r=nullptr): val(_val), l(_l), r(_r) {}
    NODE* in(int st, int fin, int k){
        if(k<st||k>fin)return this;
        if(st==fin)return new NODE(this->val+1, l, r);
        return new NODE(this->val+1, l->in(st, (st+fin)/2, k), r->in((st+fin)/2+1, fin, k));
    }
    int query(int st, int fin, int ll, int rr){
        if(rr<st||ll>fin)return 0;
        if(ll<=st&&rr>=fin)return this->val;
        return l->query(st, (st+fin)/2, ll, rr)+r->query((st+fin)/2+1, fin, ll, rr);
    }
};
NODE *root[500010];
int pos[500010], n;

void init(int N, int A[], int B[]){
    n=N;
    vector<pii> vc;
    for(int i=0; i<n; i++){
        vc.pb(mp(A[i], B[i]));
    }
    sortvec(vc);
    root[0]=new NODE(0);
    root[0]->l=root[0]->r=root[0];
    for(int i=1; i<=n; i++){
        root[i]=root[i-1]->in(1, n, vc[i-1].S);
        pos[vc[i-1].F]=i;
    }
    for(int i=1; i<=n; i++){
        if(!pos[i])pos[i]=pos[i-1];
    }
}

int can(int m, int k[]){
    sort(k, k+m);
    vector<int> vc, ch;
    for(int i=0; i<m; i++)vc.pb(k[i]);
    compress(vc);
    ch.resize(vc.size());
    int point=0, point2=0;
    for(int i=0; i<m; i++){
        while(vc[point]<k[i])point++;
        if(i&&k[i]!=k[i-1])point2=point;
        int temp=k[i];
        while(temp&&point2<vc.size()){
            int ans;
            if(point2==vc.size()-1)ans=root[pos[k[i]]]->query(1, n, vc[point2], n)-ch[point2];
            else ans=root[pos[k[i]]]->query(1, n, vc[point2], vc[point2+1]-1)-ch[point2];
            ch[point2]+=min(ans, temp);
            temp-=min(ans, temp);
            if(!temp)break;
            point2++;
        }
        if(temp)return 0;
    }
    return 1;
}

//thx a lot to short impl. of PST to gnoor

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(temp&&point2<vc.size()){
                     ~~~~~~^~~~~~~~~~
teams.cpp:62:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(point2==vc.size()-1)ans=root[pos[k[i]]]->query(1, n, vc[point2], n)-ch[point2];
                ~~~~~~^~~~~~~~~~~~~

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