oj.uz

Submission #1083618

# Submission time Handle Problem Language Result Execution time Memory
1083618 2024-09-03T15:22:43 Z vladilius Teams (IOI15_teams) C++17
100 / 100
 2527 ms 374060 KB 
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert

struct PST{
    struct node{
        node *l, *r;
        int s;
        node(int k){
            l = r = 0;
            s = k;
        }
        node(node *ls, node *rs){
            l = ls; r = rs;
            s = (l -> s) + (r -> s);
        }
    };
    vector<node*> root;
    int n, cc;
    void init(int ns){
        n = ns;
        root.resize(n + 1);
        root[0] = build(1, n);
        cc = 0;
    }
    node* build(int tl, int tr){
        if (tl == tr) return new node(0);
        int tm = (tl + tr) / 2;
        return new node(build(tl, tm), build(tm + 1, tr));
    }
    node* upd(node *v, int tl, int tr, int& x){
        if (tl == tr) return new node(v -> s + 1);
        int tm = (tl + tr) / 2;
        if (x <= tm){
            return new node(upd(v -> l, tl, tm, x), v -> r);
        }
        return new node(v -> l, upd(v -> r, tm + 1, tr, x));
    }
    void upd(int x){
        cc++;
        root[cc] = upd(root[cc - 1], 1, n, x);
    }
    int get(node *v, int tl, int tr, int& l, int& r){
        if (l > tr || r < tl) return 0;
        if (l <= tl && tr <= r) return (v -> s);
        int tm = (tl + tr) / 2;
        return get(v -> l, tl, tm, l, r) + get(v -> r, tm + 1, tr, l, r);
    }
    int get(int k, int l, int r){
        l = max(l, 1); 
        if (l > r || k <= 0) return 0;
        return get(root[k], 1, n, l, r);
    }
};
 
int n;
vector<int> a, b;
vector<pii> all;
PST T;
 
void init(int N, int A[], int B[]){
    n = N;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++) a[i] = A[i - 1];
    b.resize(n + 1);
    for (int i = 1; i <= n; i++) b[i] = B[i - 1];
    
    all.pb({0, 0});
    for (int i = 1; i <= n; i++) all.pb({b[i], a[i]});
    sort(all.begin(), all.end());
    
    for (int i = 1; i <= n; i++){
        a[i] = all[i].ss;
        b[i] = all[i].ff;
    }
    
    T.init(n);
    for (int i = 1; i <= n; i++) T.upd(a[i]);
}

vector<int> :: iterator it;

int sum(int x, int x1, int y1, int x2){
    it = lower_bound(b.begin(), b.end(), y1);
    int j = (int) (it - b.begin());
    return T.get(x, x1, x2) - T.get(j - 1, x1, x2);
}

int pr(int x, int y){
    it = upper_bound(b.begin(), b.end(), y);
    int j = (int) (it - b.begin()) - 1;
    return T.get(j, 1, x);
}

int sum1(int x1, int y1, int x2, int y2){
    if (x1 > x2 || y1 > y2) return 0;
    return pr(x2, y2) + pr(x1 - 1, y1 - 1) - pr(x1 - 1, y2) - pr(x2, y1 - 1);
}
 
int can(int m, int K[]){
    vector<int> k(m + 1);
    for (int i = 1; i <= m; i++) k[i] = K[i - 1];
    sort(k.begin() + 1, k.end());
    
    vector<pii> st;
    vector<int> pr = {0};
    
    auto add = [&](int k, int x){
        while (!st.empty() && st.back().ss <= x){
            st.pop_back();
            pr.pop_back();
        }
        
        if (st.empty()) pr.pb(sum(x, 0, 0, k));
        else pr.pb(pr.back() + sum(x, st.back().ff + 1, 0, k));
        
        st.pb({k, x});
    };
    
    auto get = [&](int k, int x){
        if (st.empty()) return sum(x, 0, k, k);
        int l = 0, r = (int) st.size() - 1;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (st[m].ss < x){
                r = m - 1;
            }
            else {
                l = m;
            }
        }
        if (st[r].ss >= x) l = r;
        if (st[l].ss < x) l = -1;
        
        int out = sum(x, 0, k, k);
        if (l != -1) out -= sum(x, 0, k, st[l].ff);
        if (l + 1 < pr.size()) out -= (pr.back() - pr[l + 1] - sum1((l != -1) ? (st[l].ff + 1) : 0, 0, st.back().ff, k - 1));
        return out;
    };

    for (int i = 1; i <= m; i++){
        while (!st.empty() && all[st.back().ss].ff < k[i]){
            st.pop_back();
            pr.pop_back();
        }

        if (get(k[i], n) < k[i]) return 0;
        
        int l = 1, r = n;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (get(k[i], m) < k[i]){
                l = m + 1;
            }
            else {
                r = m;
            }
        }
        if (get(k[i], l) == k[i]) r = l;
        
        add(k[i], r);
    }
    return 1;
}

Compilation message

teams.cpp: In lambda function:
teams.cpp:114:24: warning: declaration of 'k' shadows a previous local [-Wshadow]
  114 |     auto add = [&](int k, int x){
      |                    ~~~~^
teams.cpp:107:17: note: shadowed declaration is here
  107 |     vector<int> k(m + 1);
      |                 ^
teams.cpp: In lambda function:
teams.cpp:126:24: warning: declaration of 'k' shadows a previous local [-Wshadow]
  126 |     auto get = [&](int k, int x){
      |                    ~~~~^
teams.cpp:107:17: note: shadowed declaration is here
  107 |     vector<int> k(m + 1);
      |                 ^
teams.cpp:130:17: warning: declaration of 'int m' shadows a parameter [-Wshadow]
  130 |             int m = (l + r) / 2;
      |                 ^
teams.cpp:106:13: note: shadowed declaration is here
  106 | int can(int m, int K[]){
      |         ~~~~^
teams.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         if (l + 1 < pr.size()) out -= (pr.back() - pr[l + 1] - sum1((l != -1) ? (st[l].ff + 1) : 0, 0, st.back().ff, k - 1));
      |             ~~~~~~^~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:157:17: warning: declaration of 'int m' shadows a parameter [-Wshadow]
  157 |             int m = (l + r) / 2;
      |                 ^
teams.cpp:106:13: note: shadowed declaration is here
  106 | int can(int m, int K[]){
      |         ~~~~^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 66140 KB Output is correct
2 Correct 96 ms 66248 KB Output is correct
3 Correct 93 ms 66244 KB Output is correct
4 Correct 95 ms 67204 KB Output is correct
5 Correct 60 ms 65988 KB Output is correct
6 Correct 70 ms 65808 KB Output is correct
7 Correct 63 ms 65848 KB Output is correct
8 Correct 62 ms 65908 KB Output is correct
9 Correct 228 ms 67268 KB Output is correct
10 Correct 117 ms 66648 KB Output is correct
11 Correct 70 ms 66756 KB Output is correct
12 Correct 58 ms 66756 KB Output is correct
13 Correct 72 ms 66500 KB Output is correct
14 Correct 67 ms 66680 KB Output is correct
15 Correct 86 ms 66248 KB Output is correct
16 Correct 94 ms 66248 KB Output is correct
17 Correct 71 ms 67024 KB Output is correct
18 Correct 77 ms 67192 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 67012 KB Output is correct
2 Correct 100 ms 67012 KB Output is correct
3 Correct 411 ms 70348 KB Output is correct
4 Correct 97 ms 67080 KB Output is correct
5 Correct 346 ms 66556 KB Output is correct
6 Correct 315 ms 66760 KB Output is correct
7 Correct 64 ms 66612 KB Output is correct
8 Correct 242 ms 66724 KB Output is correct
9 Correct 216 ms 67276 KB Output is correct
10 Correct 332 ms 67272 KB Output is correct
11 Correct 357 ms 67316 KB Output is correct
12 Correct 544 ms 67528 KB Output is correct
13 Correct 584 ms 67268 KB Output is correct
14 Correct 614 ms 69064 KB Output is correct
15 Correct 324 ms 67016 KB Output is correct
16 Correct 324 ms 67084 KB Output is correct
17 Correct 314 ms 67780 KB Output is correct
18 Correct 320 ms 67784 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 367384 KB Output is correct
2 Correct 673 ms 367408 KB Output is correct
3 Correct 1840 ms 374060 KB Output is correct
4 Correct 661 ms 367788 KB Output is correct
5 Correct 1029 ms 364912 KB Output is correct
6 Correct 939 ms 365060 KB Output is correct
7 Correct 332 ms 364984 KB Output is correct
8 Correct 831 ms 364984 KB Output is correct
9 Correct 1271 ms 366264 KB Output is correct
10 Correct 1233 ms 364256 KB Output is correct
11 Correct 1547 ms 364784 KB Output is correct
12 Correct 1700 ms 365416 KB Output is correct
13 Correct 2017 ms 366848 KB Output is correct
14 Correct 2527 ms 371384 KB Output is correct
15 Correct 1142 ms 368060 KB Output is correct
16 Correct 1137 ms 368164 KB Output is correct
17 Correct 1020 ms 367804 KB Output is correct
18 Correct 993 ms 367804 KB Output is correct