제출 #537048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537048		ivan24	팀들 (IOI15_teams)	C++14	100 / 100	3313 ms	428072 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;
        ll idx = (itr-t.begin())-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 = 0, rres = 0;
            if (!(l > qr || ql > m)) lres = query(left(i),l,m,ql,qr,t);
            if (!(m+1 > qr || ql > r)) 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;
vi ctr,vals,byBucket;

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);
    }
  	ctr.assign(n,0);
 	vals.assign(n,0);
  	byBucket.assign(n,0);
}

int can(int m, int k[]) {
    sort(k,k+m);
    ll sum = 0;
    for (ll i = 0; m > i; i++) sum += k[i];
    if (sum > n) return 0;
    ctr[0]  = k[0];
  	ll ptr = 0;
    for (ll i = 1; m > i; i++){
        if (k[i] != k[i-1]) ctr[++ptr] = 0;
        ctr[ptr] += k[i];
    }
    vals[0] = k[0];
 	ptr = 0;
    for (ll i = 1; m > i; i++){
        if (k[i] != k[i-1]) vals[++ptr] = k[i];
    }
    vals[ptr+1] = n+1;
  	for (ll i = 0; ptr >= i; i++) byBucket[i] = 0;
    /*
    cout << itr->F << " " << itr->S << endl;
    cout << "vals:\n";
    for (auto i: vals) cout << i << " ";
    cout << endl;
    */
    for (ll i = 0; ptr >= i; i++){
        for (ll j = i; ptr >= j; j++){
            //cout << "i: " << i << " j: " << j << endl;
            if (ctr[i] == 0) break;
            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;
        }
        if (ctr[i] > 0) return 0;
        /*
        cout << itr->F << " " << itr->S << endl;
        for (auto i: byBucket) cout << i << " ";
        cout << endl;
        */
    }
    //cout << "1\n";
	return 1;
}

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