oj.uz

답안 #587043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
587043 2022-07-01T09:10:09 Z Lucpp 팀들 (IOI15_teams) C++17
100 / 100
 2983 ms 154040 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
const int inf = 1e6;

vector<int> S, L, R;
int upd(int p, int v, int a, int b, int i){
    int j = sz(S);
    S.push_back(S[i]);
    L.push_back(L[i]);
    R.push_back(R[i]);
    if(a==b) S[j] = v;
    else{
        int m = (a+b)/2;
        if(p <= m){
            int k = upd(p, v, a, m, L[i]);
            L[j] = k;
        }
        else{
            int k = upd(p, v, m+1, b, R[i]);
            R[j] = k;
        }
        S[j] = S[L[j]]+S[R[j]];
    }
    return j;
}
int qry(int l, int r, int a, int b, int i){
    if(l <= a && b <= r) return S[i];
    else if(b < l || r < a) return 0;
    int m = (a+b)/2;
    return qry(l, r, a, m, L[i]) + qry(l, r, m+1, b, R[i]);
}

int n, cap;
vector<int> ind, roots;

int f(int l, int r, int cnt){ // maximum i s.t. >= cnt intervals starting between l and r contain i
    int lo = 0, hi = n+1;
    for(int mid = (lo+hi+1)/2; lo<hi; mid=(lo+hi+1)/2){
        if(qry(ind[l]+1, ind[r+1], 1, cap, roots[mid]) >= cnt) lo = mid;
        else hi = mid-1;
    }
    return lo;
}

void init(int _n, int* a, int* b){
    n = _n;
    for(cap = 1; cap <= n+1; cap*=2);
    S.resize(2*cap);
    L.assign(2*cap, -1);
    R.assign(2*cap, -1);
    for(int i = cap-1; i > 0; i--) L[i] = 2*i, R[i] = 2*i+1;

    ind.resize(n+2);
    vector<pair<int, int>> p(n);
    for(int i = 0; i < n; i++) p[i] = {a[i], b[i]};
    sort(p.begin(), p.end());
    int j = 0;
    for(int i = 1; i <= n+1; i++){
        while(j < n && p[j].first < i) j++;
        ind[i] = j;
    }

    vector<pair<int, int>> q(n);
    for(int i = 0; i < n; i++) q[i] = {p[i].second, i};
    sort(q.rbegin(), q.rend());
    j = 0;
    int root = 1;
    roots.resize(n+2);
    for(int i = n+1; i >= 0; i--){
        while(j < n && q[j].first >= i){
            root = upd(q[j].second+1, 1, 1, cap, root);
            j++;
        }
        roots[i] = root;
    }
}


int can(int m, int* K){
    vector<int> v(m);
    for(int i = 0; i < m; i++) v[i] = K[i];
    sort(v.begin(), v.end());
    stack<tuple<int, int, int>> st;
    st.emplace(0, 0, inf);
    for(int x : v){
        while(get<2>(st.top()) < x) st.pop();
        auto [dp, y, good] = st.top();
        int cur = dp-x;
        cur += qry(ind[y+1]+1, ind[x+1], 1, cap, roots[x]);
        if(cur < 0) return 0;
        while(!st.empty()){
            tie(dp, y, good) = st.top();
            if(cur < dp) st.pop();
            else{
                int change = f(y+1, x, cur-dp);
                if(good < change) st.pop();
                else{
                    st.emplace(cur, x, change);
                    break;
                }
            }
        }
    }
    return 1;
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 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 300 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 300 KB Output is correct
26 Correct 1 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 28068 KB Output is correct
2 Correct 99 ms 28136 KB Output is correct
3 Correct 114 ms 28052 KB Output is correct
4 Correct 103 ms 28100 KB Output is correct
5 Correct 67 ms 27988 KB Output is correct
6 Correct 71 ms 27952 KB Output is correct
7 Correct 58 ms 28044 KB Output is correct
8 Correct 57 ms 28404 KB Output is correct
9 Correct 121 ms 28324 KB Output is correct
10 Correct 79 ms 28112 KB Output is correct
11 Correct 60 ms 28240 KB Output is correct
12 Correct 55 ms 28296 KB Output is correct
13 Correct 79 ms 28612 KB Output is correct
14 Correct 71 ms 28628 KB Output is correct
15 Correct 93 ms 28720 KB Output is correct
16 Correct 83 ms 28684 KB Output is correct
17 Correct 62 ms 28744 KB Output is correct
18 Correct 66 ms 28732 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 28228 KB Output is correct
2 Correct 100 ms 28072 KB Output is correct
3 Correct 537 ms 30520 KB Output is correct
4 Correct 99 ms 28236 KB Output is correct
5 Correct 319 ms 27936 KB Output is correct
6 Correct 296 ms 28644 KB Output is correct
7 Correct 79 ms 28568 KB Output is correct
8 Correct 242 ms 28656 KB Output is correct
9 Correct 136 ms 28476 KB Output is correct
10 Correct 224 ms 28220 KB Output is correct
11 Correct 204 ms 28416 KB Output is correct
12 Correct 241 ms 28476 KB Output is correct
13 Correct 453 ms 28712 KB Output is correct
14 Correct 725 ms 29832 KB Output is correct
15 Correct 326 ms 28820 KB Output is correct
16 Correct 291 ms 28820 KB Output is correct
17 Correct 297 ms 28832 KB Output is correct
18 Correct 322 ms 28884 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 752 ms 148648 KB Output is correct
2 Correct 758 ms 148508 KB Output is correct
3 Correct 2040 ms 148584 KB Output is correct
4 Correct 703 ms 148504 KB Output is correct
5 Correct 1205 ms 148488 KB Output is correct
6 Correct 1034 ms 149216 KB Output is correct
7 Correct 371 ms 149348 KB Output is correct
8 Correct 1164 ms 151548 KB Output is correct
9 Correct 777 ms 151928 KB Output is correct
10 Correct 838 ms 150036 KB Output is correct
11 Correct 837 ms 150556 KB Output is correct
12 Correct 1020 ms 151068 KB Output is correct
13 Correct 1990 ms 152676 KB Output is correct
14 Correct 2983 ms 153972 KB Output is correct
15 Correct 1147 ms 154004 KB Output is correct
16 Correct 1097 ms 154040 KB Output is correct
17 Correct 976 ms 153412 KB Output is correct
18 Correct 952 ms 153424 KB Output is correct