Submission #536635

#	Time	Username	Problem	Language	Result	Execution time	Memory
536635		ivan24	Teams (IOI15_teams)	C++14	77 / 100	4067 ms	416092 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

ll min (ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

struct PNode {
    vi v,t;
    ll qry (ll curt){
        /*
        cout << "queried: " << curt << "\n";
        for (auto i: v) cout << i << " ";
        cout << endl;
        for (auto i: t) cout << i << " ";
        cout << endl;
        */
        auto itr = upper_bound(t.begin(),t.end(),curt);
        ll idx = distance(t.begin(),itr)-1;
        //cout << v[idx] << endl;
        return v[idx];
    }
    ll lst_qry(){
        return v.back();
    }
    void inc_update (ll vn, ll tn){
        if (t.back() != tn){
            v.push_back(lst_qry()+vn);
            t.push_back(tn);
        }else{
            v[v.size()-1] += vn;
        }
    }
    void change_update (ll vn, ll tn){
        if (t.back() != tn){
            v.push_back(vn);
            t.push_back(tn);
        }else{
            v[v.size()-1] = vn;
        }
    }
    PNode (){ v = vi{0}; t = vi{0}; }
};

class SegTree {
private:
    vector<PNode> st;
    ll n;
    ll left (ll x){ return (x << 1) ; }
    ll right (ll x){ return (x << 1) + 1; }
    void update (ll i, ll l, ll r, ll idx, ll inc, ll t){
        // assumed that t is updated increasingly
        if (r >= idx && idx >= l){
            if (l == r){
                st[i].inc_update(inc,t);
            }else{
                //cout << i << " " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
                ll m = (l+r)/2;
                update(left(i),l,m,idx,inc,t);
                update(right(i),m+1,r,idx,inc,t);
                st[i].change_update(st[left(i)].lst_qry()+st[right(i)].lst_qry(),t);
            }

            //cout << i << " " << t << " , " << l << " -> " << r << " : " << st[i].lst_qry() << endl;
        }
    }
    ll query (ll i, ll l, ll r, ll ql, ll qr, ll t){
        //cout << i << " " << l << " " << r << " " << ql << " " << qr << endl;
        if (qr >= r && l >= ql){
            /*
            cout << "queried: \n";
            cout << "params: " << i << " " << l << " " << r << endl;
            cout << "result: " << st[i].qry(t) << endl;
            */
            return st[i].qry(t);
        }else if (l > qr || ql > r){
            return 0;
        }else{
            ll m = (l+r)/2;
            ll lres = query(left(i),l,m,ql,qr,t);
            ll rres = query(right(i),m+1,r,ql,qr,t);
            return lres+rres;
        }
    }
public:
    SegTree (){}
    SegTree(ll _n): n(_n){
        st.resize(4*n);
    }
    void update (ll idx, ll inc, ll t){
        update(1,0,n-1,idx,inc,t);
    }
    ll query (ll ql, ll qr, ll t){
        return query(1,0,n-1,ql,qr,t);
    }
};

SegTree st;
ll n;

void init(int _n, int a[], int b[]) {
    n = _n;
    st = SegTree(n+1);
    vii itvls;
    for (ll i = 0; n > i; i++) itvls.emplace_back(a[i],b[i]);
    sort(itvls.begin(),itvls.end());

    for (auto i: itvls){
        //cout << i.F << " " << i.S << endl;
        st.update(i.S,1,i.F);
    }
}

int can(int m, int k[]) {
    sort(k,k+m);
    vi ctr;
    ctr.push_back(k[0]);
    for (ll i = 1; m > i; i++){
        if (k[i] != k[i-1]) ctr.push_back(0);
        ctr[ctr.size()-1] += k[i];
    }
    vi vals;
    vals.push_back(k[0]);
    for (ll i = 1; m > i; i++){
        if (k[i] != k[i-1]) vals.push_back(k[i]);
    }
    vals.push_back(n+1);
    vi byBucket;
    byBucket.assign(vals.size(),0);
    /*
    cout << itr->F << " " << itr->S << endl;
    cout << "vals:\n";
    for (auto i: vals) cout << i << " ";
    cout << endl;
    */
    for (ll i = 0; vals.size() > i+1; i++){
        for (ll j = i; vals.size() > j+1; j++){
            //cout << "i: " << i << " j: " << j << endl;
            ll rmv = st.query(vals[j],vals[j+1]-1,vals[i])-byBucket[j];
            //cout << vals[j] << " " << vals[j+1] << " " << vals[i] << ": " << rmv << endl;
            //cout << "itr: " << itr->F << " " << itr->S << endl;
            rmv = min(rmv,ctr[i]);
            ctr[i] -= rmv;
            byBucket[j] += rmv;
        }
        /*
        cout << itr->F << " " << itr->S << endl;
        for (auto i: byBucket) cout << i << " ";
        cout << endl;
        */
    }

    for (auto i: ctr){
        //cout << i.F << " " << i.S << endl;
        if (i > 0){ return 0; }
    }
    //cout << "1\n";
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:150:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  150 |     for (ll i = 0; vals.size() > i+1; i++){
      |                    ~~~~~~~~~~~~^~~~~
teams.cpp:151:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  151 |         for (ll j = i; vals.size() > j+1; j++){
      |                        ~~~~~~~~~~~~^~~~~

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