Submission #1083618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083618		vladilius	Teams (IOI15_teams)	C++17	100 / 100	2527 ms	374060 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23