oj.uz

Submission #604300

# Submission time Handle Problem Language Result Execution time Memory
604300 2022-07-25T03:08:55 Z wiwiho Teams (IOI15_teams) C++14
100 / 100
 1961 ms 266884 KB 
#include "teams.h"

#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define ef emplace_front
#define pob pop_back()
#define pof pop_front()
#define mp make_pair
#define F first
#define S second
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b){ \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node{
    int v = 0, l = -1, r = -1, tme = 0;
};

vector<Node> st;
vector<int> rt;
int ts = 0;
int n;

int build(int L, int R){
    int id = ts++;
    if(L == R) return id;
    int M = (L + R) / 2;
    st[id].l = build(L, M);
    st[id].r = build(M + 1, R);
    return id;
}

int modify(int x, int L, int R, int oid, int tme){
    int id = oid;
    if(st[id].tme < tme){
        id = ts++;
        st[id] = st[oid];
        st[id].tme = tme;
    }
    if(L == R){
        st[id].v++;
        return id;
    }
    int M = (L + R) / 2;
    if(x <= M) st[id].l = modify(x, L, M, st[id].l, tme);
    else st[id].r = modify(x, M + 1, R, st[id].r, tme);
    st[id].v = st[st[id].l].v + st[st[id].r].v;
    return id;
}

int query(int l, int r, int L, int R, int id){
    //cerr << "query " << l << " " << r << " " << L << " " << R << " " << id << "\n";
    if(l <= L && R <= r){
        //cerr << "OAO\n";
        return st[id].v;
    }
    int M = (L + R) / 2;
    if(r <= M) return query(l, r, L, M, st[id].l);
    else if(l > M) return query(l, r, M + 1, R, st[id].r);
    else return query(l, r, L, M, st[id].l) + query(l, r, M + 1, R, st[id].r);
}

void init(int _n, int A[], int B[]){
    n = _n;
    st.resize(30 * n);
    rt.resize(n + 1);
    rt[0] = build(1, n);

    vector<vector<int>> pos(n + 1);
    for(int i = 0; i < n; i++){
        pos[B[i]].eb(A[i]);
    }
    for(int i = 1; i <= n; i++){
        rt[i] = rt[i - 1];
        for(int j : pos[i]){
            rt[i] = modify(j, 1, n, rt[i], i);
        }
    }
    //cerr << "ok\n";
}

struct seg{
    int l, r, cnt = 0, y = 0, up = n;
};

ostream& operator<<(ostream& o, seg s){
    return o << '(' << s.l << ',' << s.r << ',' << s.cnt << ',' << s.y << ',' << s.up << ')';
}

int can(int m, int _K[]){

    vector<int> K(m);
    for(int i = 0; i < m; i++){
        K[i] = _K[i];
    }
    lsort(K);
    //cerr << "can " << m << " : ";
    //printv(K, cerr);

    deque<seg> dq;
    for(int i : K){
        if(dq.empty()){
            dq.eb(seg({1, i, 0, 0, n}));
        }
        else if(dq.back().r < i){
            dq.eb(seg({dq.back().r + 1, i, 0, 0, dq.back().y - 1}));
        }

        //cerr << "test " << i << "\n";
        //printv(dq, cerr);

        int cnt = 0;
        bool ok = false;
        while(!dq.empty()){
            //cerr << "owo\n";
            seg now = dq.back();
            dq.pob;
            int l = now.l, r = now.r;
            cnt += max(now.cnt, query(l, r, 1, n, rt[i - 1]));
            //cerr << "test " << now << " " << cnt << "\n";
            int need = cnt + i;
            if(query(l, i, 1, n, rt[now.up]) < need) continue;
            ok = true;

            int lr = 1, rr = now.up;
            while(lr < rr){
                //cerr << "binary search " << lr << " " << rr << "\n";
                int mid = (lr + rr) / 2;
                if(query(l, i, 1, n, rt[mid]) >= need) rr = mid;
                else lr = mid + 1;
            }

            dq.eb(seg({l, i, need, lr, now.up}));
            break;
        }
        //cerr << "ok ";
        //printv(dq, cerr);
        if(!ok) return 0;

    }

	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 0 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 1 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 304 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 296 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 52556 KB Output is correct
2 Correct 74 ms 52464 KB Output is correct
3 Correct 75 ms 52520 KB Output is correct
4 Correct 79 ms 52456 KB Output is correct
5 Correct 43 ms 51412 KB Output is correct
6 Correct 42 ms 51404 KB Output is correct
7 Correct 47 ms 51412 KB Output is correct
8 Correct 48 ms 52180 KB Output is correct
9 Correct 67 ms 52168 KB Output is correct
10 Correct 55 ms 51912 KB Output is correct
11 Correct 43 ms 52008 KB Output is correct
12 Correct 42 ms 52016 KB Output is correct
13 Correct 47 ms 52456 KB Output is correct
14 Correct 54 ms 52936 KB Output is correct
15 Correct 71 ms 53548 KB Output is correct
16 Correct 68 ms 53440 KB Output is correct
17 Correct 44 ms 52376 KB Output is correct
18 Correct 45 ms 52420 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 52568 KB Output is correct
2 Correct 84 ms 52640 KB Output is correct
3 Correct 405 ms 52564 KB Output is correct
4 Correct 81 ms 52556 KB Output is correct
5 Correct 162 ms 51464 KB Output is correct
6 Correct 146 ms 51420 KB Output is correct
7 Correct 47 ms 51368 KB Output is correct
8 Correct 118 ms 52400 KB Output is correct
9 Correct 69 ms 52248 KB Output is correct
10 Correct 112 ms 52020 KB Output is correct
11 Correct 150 ms 52060 KB Output is correct
12 Correct 166 ms 52296 KB Output is correct
13 Correct 236 ms 52604 KB Output is correct
14 Correct 522 ms 53504 KB Output is correct
15 Correct 177 ms 53680 KB Output is correct
16 Correct 158 ms 53652 KB Output is correct
17 Correct 143 ms 52556 KB Output is correct
18 Correct 141 ms 52508 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 261704 KB Output is correct
2 Correct 590 ms 261716 KB Output is correct
3 Correct 1535 ms 261716 KB Output is correct
4 Correct 563 ms 261716 KB Output is correct
5 Correct 521 ms 255832 KB Output is correct
6 Correct 454 ms 255840 KB Output is correct
7 Correct 224 ms 255924 KB Output is correct
8 Correct 422 ms 259876 KB Output is correct
9 Correct 353 ms 259536 KB Output is correct
10 Correct 408 ms 257532 KB Output is correct
11 Correct 456 ms 258072 KB Output is correct
12 Correct 569 ms 258584 KB Output is correct
13 Correct 927 ms 260760 KB Output is correct
14 Correct 1961 ms 266884 KB Output is correct
15 Correct 656 ms 266640 KB Output is correct
16 Correct 667 ms 266788 KB Output is correct
17 Correct 456 ms 261644 KB Output is correct
18 Correct 437 ms 261304 KB Output is correct