Submission #588585

#	Time	Username	Problem	Language	Result	Execution time	Memory
588585		Do_you_copy	Teams (IOI15_teams)	C++14	0 / 100	1186 ms	370684 KiB

teams

#include <bits/stdc++.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 = 5e5 + 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; vector <int> v(mm + 1, 0);
    for (int i = 0; i < mm; ++i) v[i + 1] = kk[i];
    sort(v.begin(), v.end());
    int last = 0, remaining = 0;
    for (int i = 1; i <= mm; ++i){
        int to = upper_bound(a + 1, a + n + 1, v[i],[](const auto &ii, const auto &jj){
            return ii < jj.l;
        }) - a - 1;
        if (to == 0) return 0;
        int total = (get(root[0], root[to], v[i]));
        int right = (last != to) ? (get(root[last], root[to], v[i])) : 0;
        int left = total - right;
        left = min(left, remaining);
        if (left + right < v[i]) return 0;
        remaining = left + right - v[i];
        last = to;
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:73:23: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   73 | void init(int N, int *ll, int *rr){
      |                  ~~~~~^~
teams.cpp:8:7: note: shadowed declaration is here
    8 | using ll = long long;
      |       ^~
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, v[i],[](const auto &ii, const auto &jj){
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   93 |             return ii < jj.l;
      |             ~~~~~~~~~~~~~~~~~
   94 |         }) - a - 1;
      |         ~~~~~~~^~~

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