Submission #1083228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083228		vladilius	Teams (IOI15_teams)	C++17	0 / 100	4099 ms	32956 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
 
int n;
vector<int> a, b;
vector<vector<int>> d;
vector<pii> st;
 
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];
    
    for (int i = 1; i <= n; i++) st.pb({a[i], b[i]});
    d.resize(n + 1);
    for (int i = 1; i <= n; i++) d[b[i]].pb(a[i]);
    sort(st.begin(), st.end());
}
 
int pr(int x, int y){
    int out = 0;
    for (auto [u, v]: st){
        out += (u <= x && v <= y);
    }
    return out;
}
 
int sum(int x1, int y1, int x2, int y2){
    return pr(x2, y2) + pr(x1, y1) - pr(x1 - 1, y2) - pr(x2, y1 - 1);
}

vector<int> :: iterator it1, it2;
 
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 get = [&](int x, int y){
        if (st.empty()) return sum(0, x, x, y);
        int l = 0, r = (int) st.size() - 1;
        while (l + 1 < r){
            int m = (l + r) / 2;
            if (st[m].ss >= y){
                l = m;
            }
            else {
                r = m - 1;
            }
        }
        if (st[r].ss >= y) l = r;
        if (st[l].ss < y) l = -1;
        
        int out = sum(0, x, x, y);
        for (int i = 0; i + 1 < st.size(); i++){
            out -= sum(st[i].ff + 1, x, st[i + 1].ff, min(st[i + 1].ss, y));
        }
        out -= sum(0, x, st[0].ff, min(st[0].ss, y));
        
        // if (l != -1) out -= sum(0, x, st[l].ff, y);
        // if (l + 1 < pr.size()) out -= (pr.back() - pr[l + 1] - sum((l != -1) ? (st[l].ff + 1) : 0, 0, x, x - 1));
        
        return out;
    };
    
    auto add = [&](int x, int y){
        while (!st.empty() && st.back().ss < y){
            st.pop_back();
            pr.pop_back();
        }
        
        if (st.empty()) pr.pb(sum(0, 0, x, y));
        else pr.pb(pr.back() + sum(st.back().ff + 1, 0, x, y));
        
        st.pb({x, y});
    };
    
    for (int i = 1; i <= m; i++){
        while (!st.empty() && st.back().ss < k[i]){
            st.pop_back();
            pr.pop_back();
        }
        
        if (get(k[i], n) < k[i]) return 0;
        int l = k[i], 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;
        
        if (get(k[i], r) == k[i]){
            add(k[i], r);
            continue;
        }
        
        while (true) k[i]++;
        
        int t = k[i];
        
        k[i] -= get(k[i], r - 1);
        
        int j = 0;
        while (j < st.size() && st[j].ss >= r){
            j++;
        }
        int p = (st.empty() || !j) ? 0 : st[j - 1].ff; p++;
        
        auto check = [&](int m){
            it1 = lower_bound(d[r].begin(), d[r].end(), p);
            it2 = upper_bound(d[r].begin(), d[r].end(), m);
            return (it2 - it1);
        };
        
        int l1 = p, r1 = n;
        while (l1 + 1 < r1){
            int m = (l1 + r1) / 2;
            if (check(m) < k[i]){
                l1 = m + 1;
            }
            else {
                r1 = m;
            }
        }
        if (check(l1) == k[i]) r1 = l1;
        
        add(r1, r);
        add(t, r - 1);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:48:17: warning: declaration of 'st' shadows a global declaration [-Wshadow]
   48 |     vector<pii> st;
      |                 ^~
teams.cpp:14:13: note: shadowed declaration is here
   14 | vector<pii> st;
      |             ^~
teams.cpp: In lambda function:
teams.cpp:55:17: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   55 |             int m = (l + r) / 2;
      |                 ^
teams.cpp:43:13: note: shadowed declaration is here
   43 | int can(int m, int K[]){
      |         ~~~~^
teams.cpp:67:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for (int i = 0; i + 1 < st.size(); i++){
      |                         ~~~~~~^~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:99:17: warning: declaration of 'int m' shadows a parameter [-Wshadow]
   99 |             int m = (l + r) / 2;
      |                 ^
teams.cpp:43:13: note: shadowed declaration is here
   43 | int can(int m, int K[]){
      |         ~~~~^
teams.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         while (j < st.size() && st[j].ss >= r){
      |                ~~^~~~~~~~~~~
teams.cpp: In lambda function:
teams.cpp:126:30: warning: declaration of 'int m' shadows a parameter [-Wshadow]
  126 |         auto check = [&](int m){
      |                          ~~~~^
teams.cpp:43:13: note: shadowed declaration is here
   43 | int can(int m, int K[]){
      |         ~~~~^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:134:17: warning: declaration of 'int m' shadows a parameter [-Wshadow]
  134 |             int m = (l1 + r1) / 2;
      |                 ^
teams.cpp:43:13: note: shadowed declaration is here
   43 | int can(int m, int K[]){
      |         ~~~~^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23