oj.uz

Submission #588585

# Submission time Handle Problem Language Result Execution time Memory
588585 2022-07-03T15:26:16 Z Do_you_copy Teams (IOI15_teams) C++14
0 / 100
 1186 ms 370684 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 64252 KB Output is correct
2 Correct 146 ms 64216 KB Output is correct
3 Correct 131 ms 64264 KB Output is correct
4 Correct 109 ms 64992 KB Output is correct
5 Correct 74 ms 64288 KB Output is correct
6 Correct 76 ms 64220 KB Output is correct
7 Incorrect 78 ms 64300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 64688 KB Output is correct
2 Correct 114 ms 64636 KB Output is correct
3 Correct 221 ms 67548 KB Output is correct
4 Correct 113 ms 65032 KB Output is correct
5 Correct 126 ms 64796 KB Output is correct
6 Correct 122 ms 64716 KB Output is correct
7 Incorrect 101 ms 64600 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 357100 KB Output is correct
2 Correct 791 ms 363824 KB Output is correct
3 Correct 1186 ms 370684 KB Output is correct
4 Correct 796 ms 363388 KB Output is correct
5 Correct 456 ms 361076 KB Output is correct
6 Correct 484 ms 361072 KB Output is correct
7 Incorrect 464 ms 361144 KB Output isn't correct
8 Halted 0 ms 0 KB -