Submission #588570

#	Time	Username	Problem	Language	Result	Execution time	Memory
588570		Do_you_copy	Teams (IOI15_teams)	C++14	0 / 100	541 ms	69560 KiB

teams

#include <bits/stdc++.h>
#include <teams.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const ll Mod2 = 999999999989;
const int maxN = 1e5 + 1;

int n, mm;

struct TPerson{
    int l, r;
    bool operator < (const TPerson &other){
        return l < other.l;
    }
};
TPerson a[maxN];

struct TNode{
    TNode *l, *r;
    int val;
    TNode(const int &x) : l(nullptr), r(nullptr), val(x){}
    TNode(TNode* i, TNode* j){
        l = i; r = j; val = 0;
        if (l) val += l->val;
        if (r) val += r->val;
    }
};

TNode* root[maxN];
TNode* build(int l = 1, int r = n){
    if (l == r) return new TNode(0);
    int m = (l + r) / 2;
    return new TNode(build(l, m), build(m + 1, r));
}

TNode* update(TNode* id, int i, int x, int l = 1, int r = n){
    if (l == r) return new TNode(id->val + x);
    int m = (l + r) / 2;
    if (m >= i) return new TNode(update(id->l, i, x, l, m), id->r);
    else return new TNode(id->l, update(id->r, i, x, m + 1, r));
}

bool havesex = 1;

int get(TNode* left, TNode* right, int k, int l = 1, int r = n){
    //get to find how many numbers are there equal or bigger than k
    if (r < k) return 0;
    if (k <= l) return right->val - left->val;
    int m = (l + r) / 2;
    return get(left->l, right->l, k, l, m) + get(left->r, right->r, k, m + 1, r);
}

void init(int N, int *ll, int *rr){
    n = N;
    for (int i = 0; i < n; ++i){
        a[i + 1].l = ll[i];
        a[i + 1].r = rr[i];
    }
    sort(a + 1, a + n + 1);
    root[0] = build();
    for (int i = 1; i <= n; ++i){
        root[i] = update(root[i - 1], a[i].r, 1);
    }
}

int can(int M, int *kk){
    mm = M;
    int from = 1;
    sort(kk, kk + mm);
    for (int i = 0; i < mm; ++i){
        int to = upper_bound(a + 1, a + n + 1, kk[i],[](const auto &i, const auto &j){
            return i < j.l;
        }) - a - 1;
        if (to < from) return 0;
        if (get(root[from - 1], root[to], kk[i]) < kk[i]) return 0;
        if (from == to){
            from = to + 1; continue;
        }
        int l = from, r = to;
        while (l <= r){
            int m = (l + r) / 2;
            if (get(root[from - 1], root[m], kk[i]) < kk[i]){
                //unavailable
                l = m + 1;
            }
            else r = m - 1;
        }
        from = r + 2;
    }
    return 1;
}

/*int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        int a[] = {1, 2, 2, 2}, b[] = {2, 3, 3, 4};
        init(4, a, b);
    }
    int k[] = {1, 3};
    can(2, k);
}
*/

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:23: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   74 | void init(int N, int *ll, int *rr){
      |                  ~~~~~^~
teams.cpp:9:7: note: shadowed declaration is here
    9 | using ll = long long;
      |       ^~
teams.cpp: In lambda function:
teams.cpp:92:69: warning: declaration of 'i' shadows a previous local [-Wshadow]
   92 |         int to = upper_bound(a + 1, a + n + 1, kk[i],[](const auto &i, const auto &j){
      |                                                         ~~~~~~~~~~~~^
teams.cpp:91:14: note: shadowed declaration is here
   91 |     for (int i = 0; i < mm; ++i){
      |              ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:94:16: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   92 |         int to = upper_bound(a + 1, a + n + 1, kk[i],[](const auto &i, const auto &j){
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   93 |             return i < j.l;
      |             ~~~~~~~~~~~~~~~
   94 |         }) - a - 1;
      |         ~~~~~~~^~~

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