oj.uz

Submission #386745

# Submission time Handle Problem Language Result Execution time Memory
386745 2021-04-07T09:12:31 Z ParsaAlizadeh Teams (IOI15_teams) C++17
100 / 100
 1710 ms 451708 KB 
#include <bits/stdc++.h>
#include "teams.h"
using namespace std;

typedef pair<int, int> pii;

struct Node {
    int cnt;
    Node *lc, *rc;

    Node() : cnt(0), lc(this), rc(this) {}

    Node* add(int l, int r, int ind) {
        if (ind < l || r <= ind)
            return this;
        Node* cur = new Node();
        if (r - l == 1) {
            cur->cnt = cnt + 1;
            return cur;
        }
        int mid = (l + r) >> 1;
        cur->lc = lc->add(l, mid, ind);
        cur->rc = rc->add(mid, r, ind);
        cur->cnt = cnt + 1;
        return cur; 
    }

    int get(Node* prv, int l, int r, int qr) {
        if (qr <= l)
            return 0;
        if (r <= qr)
            return cnt - prv->cnt;
        int mid = (l + r) >> 1;
        return lc->get(prv->lc, l, mid, qr) + rc->get(prv->rc, mid, r, qr);
    }

    int query(Node* prv, int l, int r, int t) {
        if (cnt - prv->cnt < t)
            return r;
        if (r - l == 1)
            return l;
        int mid = (l + r) >> 1;
        int lft = lc->cnt - prv->lc->cnt;
        if (lft >= t)
            return lc->query(prv->lc, l, mid, t);
        return rc->query(prv->rc, mid, r, t - lft);
    }

    Node* sub(Node* prv, int l, int r, int qr) {
        if (qr <= l)
            return prv;
        if (r <= qr)
            return this;
        int mid = (l + r) >> 1;
        Node* cur = new Node();
        cur->lc = lc->sub(prv->lc, l, mid, qr);
        cur->rc = rc->sub(prv->rc, mid, r, qr);
        cur->cnt = cur->lc->cnt + cur->rc->cnt;
        return cur;
    }
};

int n;
vector<Node*> root;
vector<int> R;
vector<pii> vec;

void init(int n, int A[], int B[]) {
    ::n = n;
    for (int i = 0; i < n; i++) {
        vec.emplace_back(B[i], A[i]);
    }
    sort(begin(vec), end(vec));
    vector<int> L[n];
    for (int i = 0; i < n; i++) {
        L[vec[i].second - 1].push_back(i);
    }
    root.resize(n + 1);
    R.resize(n + 1);
    root[0] = new Node();
    for (int i = 0; i < n; i++) {
        root[i + 1] = root[i];
        for (int j : L[i]) {
            root[i + 1] = root[i + 1]->add(0, n, j);
        }
        R[i + 1] = lower_bound(begin(vec), end(vec), pii{i + 1, -1}) - begin(vec);
    }
}

int can(int M, int K[]) {
    sort(K, K + M);
    Node* cur = new Node();
    for (int i = 0; i < M; i++) {
        int t = root[K[i]]->get(cur, 0, n, R[K[i]]);
        int qr = root[K[i]]->query(cur, 0, n, t + K[i]);
        if (qr == n || vec[qr].first < K[i])
            return 0;
        cur = root[K[i]]->sub(cur, 0, n, qr + 1);
    }
    return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:68:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   68 | void init(int n, int A[], int B[]) {
      |                                  ^
teams.cpp:63:5: note: shadowed declaration is here
   63 | int n;
      |     ^
teams.cpp:86:70: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   86 |         R[i + 1] = lower_bound(begin(vec), end(vec), pii{i + 1, -1}) - begin(vec);
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 3 ms 1152 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 2 ms 492 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 62560 KB Output is correct
2 Correct 164 ms 62560 KB Output is correct
3 Correct 159 ms 62560 KB Output is correct
4 Correct 159 ms 62688 KB Output is correct
5 Correct 105 ms 61408 KB Output is correct
6 Correct 103 ms 61408 KB Output is correct
7 Correct 109 ms 61408 KB Output is correct
8 Correct 103 ms 61636 KB Output is correct
9 Correct 146 ms 77536 KB Output is correct
10 Correct 119 ms 70112 KB Output is correct
11 Correct 103 ms 62048 KB Output is correct
12 Correct 99 ms 61536 KB Output is correct
13 Correct 112 ms 61664 KB Output is correct
14 Correct 140 ms 62048 KB Output is correct
15 Correct 148 ms 62688 KB Output is correct
16 Correct 146 ms 62688 KB Output is correct
17 Correct 104 ms 61684 KB Output is correct
18 Correct 108 ms 61600 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 62560 KB Output is correct
2 Correct 165 ms 62688 KB Output is correct
3 Correct 374 ms 92128 KB Output is correct
4 Correct 167 ms 62688 KB Output is correct
5 Correct 238 ms 110304 KB Output is correct
6 Correct 220 ms 103648 KB Output is correct
7 Correct 113 ms 61408 KB Output is correct
8 Correct 198 ms 93280 KB Output is correct
9 Correct 142 ms 77628 KB Output is correct
10 Correct 228 ms 110688 KB Output is correct
11 Correct 240 ms 110560 KB Output is correct
12 Correct 312 ms 110680 KB Output is correct
13 Correct 355 ms 109776 KB Output is correct
14 Correct 421 ms 99424 KB Output is correct
15 Correct 234 ms 99936 KB Output is correct
16 Correct 234 ms 99688 KB Output is correct
17 Correct 190 ms 100576 KB Output is correct
18 Correct 243 ms 100704 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 347220 KB Output is correct
2 Correct 1088 ms 347160 KB Output is correct
3 Correct 1684 ms 407380 KB Output is correct
4 Correct 1132 ms 347356 KB Output is correct
5 Correct 958 ms 450700 KB Output is correct
6 Correct 956 ms 436444 KB Output is correct
7 Correct 600 ms 340820 KB Output is correct
8 Correct 822 ms 417620 KB Output is correct
9 Correct 775 ms 432724 KB Output is correct
10 Correct 864 ms 451588 KB Output is correct
11 Correct 983 ms 451648 KB Output is correct
12 Correct 1047 ms 451708 KB Output is correct
13 Correct 1325 ms 449944 KB Output is correct
14 Correct 1710 ms 425120 KB Output is correct
15 Correct 1089 ms 427092 KB Output is correct
16 Correct 1062 ms 429524 KB Output is correct
17 Correct 781 ms 426452 KB Output is correct
18 Correct 789 ms 425044 KB Output is correct