oj.uz

Submission #537048

# Submission time Handle Problem Language Result Execution time Memory
537048 2022-03-14T10:22:51 Z ivan24 Teams (IOI15_teams) C++14
100 / 100
 3313 ms 428072 KB 
#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.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 83072 KB Output is correct
2 Correct 315 ms 83120 KB Output is correct
3 Correct 320 ms 83104 KB Output is correct
4 Correct 270 ms 83144 KB Output is correct
5 Correct 81 ms 49088 KB Output is correct
6 Correct 90 ms 49028 KB Output is correct
7 Correct 73 ms 49036 KB Output is correct
8 Correct 74 ms 49068 KB Output is correct
9 Correct 73 ms 48904 KB Output is correct
10 Correct 77 ms 48904 KB Output is correct
11 Correct 97 ms 48824 KB Output is correct
12 Correct 79 ms 49092 KB Output is correct
13 Correct 87 ms 53856 KB Output is correct
14 Correct 117 ms 58760 KB Output is correct
15 Correct 250 ms 76860 KB Output is correct
16 Correct 232 ms 76624 KB Output is correct
17 Correct 82 ms 49468 KB Output is correct
18 Correct 88 ms 49516 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 83004 KB Output is correct
2 Correct 320 ms 83004 KB Output is correct
3 Correct 444 ms 83156 KB Output is correct
4 Correct 275 ms 82936 KB Output is correct
5 Correct 94 ms 48912 KB Output is correct
6 Correct 102 ms 48956 KB Output is correct
7 Correct 88 ms 48948 KB Output is correct
8 Correct 97 ms 48936 KB Output is correct
9 Correct 77 ms 48760 KB Output is correct
10 Correct 82 ms 48784 KB Output is correct
11 Correct 104 ms 48784 KB Output is correct
12 Correct 1055 ms 49044 KB Output is correct
13 Correct 415 ms 53924 KB Output is correct
14 Correct 413 ms 78048 KB Output is correct
15 Correct 297 ms 76820 KB Output is correct
16 Correct 255 ms 76692 KB Output is correct
17 Correct 104 ms 49552 KB Output is correct
18 Correct 102 ms 49500 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1932 ms 427972 KB Output is correct
2 Correct 1917 ms 427980 KB Output is correct
3 Correct 2189 ms 427924 KB Output is correct
4 Correct 1793 ms 428072 KB Output is correct
5 Correct 454 ms 243424 KB Output is correct
6 Correct 477 ms 247376 KB Output is correct
7 Correct 433 ms 247304 KB Output is correct
8 Correct 422 ms 247464 KB Output is correct
9 Correct 453 ms 247548 KB Output is correct
10 Correct 381 ms 245700 KB Output is correct
11 Correct 1797 ms 246244 KB Output is correct
12 Correct 3313 ms 249012 KB Output is correct
13 Correct 1471 ms 273820 KB Output is correct
14 Correct 2089 ms 414188 KB Output is correct
15 Correct 1371 ms 377944 KB Output is correct
16 Correct 1382 ms 378232 KB Output is correct
17 Correct 533 ms 252860 KB Output is correct
18 Correct 467 ms 252760 KB Output is correct