oj.uz

Submission #550972

# Submission time Handle Problem Language Result Execution time Memory
550972 2022-04-19T15:10:36 Z elazarkoren Teams (IOI15_teams) C++17
100 / 100
 3269 ms 154188 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 5e5 + 5;

struct Seg{
    vi seg;
    vi l, r;
    inline void Add() {
        seg.push_back(0), l.push_back(0), r.push_back(0);
    }
    Seg() {
        Add();
    }
    inline void Fix(int i) {
        if (!l[i]) {
            l[i] = seg.size();
            Add();
            r[i] = seg.size();
            Add();
        }
    }
    int update(int i, int ind, int L, int R) {
        int copy = seg.size();
        Add();
        seg[copy] = seg[ind];
        if (L + 1 == R) {
            seg[copy]++;
            return copy;
        }
        Fix(ind);
        l[copy] = l[ind], r[copy] = r[ind];
        if (i < (L + R) >> 1) {
            int j = update(i, l[ind], L, (L + R) >> 1);
            l[copy] = j;
        } else {
            int j = update(i, r[ind], (L + R) >> 1, R);
            r[copy] = j;
        }
        seg[copy] = seg[l[copy]] + seg[r[copy]];
        return copy;
    }
    int query(int a, int b, int ind, int L, int R) {
        if (a <= L && R <= b) return seg[ind];
        if (R <= a || b <= L) return 0;
        int x1 = l[ind] ? query(a, b, l[ind], L, (L + R) >> 1) : 0;
        int x2 = r[ind] ? query(a, b, r[ind], (L + R) >> 1, R) : 0;
        return x1 + x2;
    }
};

int a[MAX_N], b[MAX_N], ind[MAX_N];
int n;

Seg seg;
int roots[MAX_N];

void init(int N, int A[], int B[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        a[i] = A[i];
        b[i] = B[i];
        ind[i] = i;
    }
    sort(ind, ind + n, [&] (int i, int j) {
        return (a[i] == a[j] ? b[i] < b[j] : a[i] < a[j]);
    });
    for (int i = 1, j = 0; i <= n; i++) {
        roots[i] = roots[i - 1];
        for (; j < n && a[ind[j]] <= i; j++) {
            roots[i] = seg.update(b[ind[j]], roots[i], 1, n + 1);
        }
    }
}

int can(int m, int k[]) {
    sort(k, k + m);
    ll s = 0;
    vii v;
    for (int i = 0; i < m; i++) {
        int j = i;
        while (j + 1 < m && k[j + 1] == k[j]) j++;
        v.push_back({k[i], (j - i + 1) * k[i]});
        s += k[i] * (j - i + 1);
        i = j;
    }
    if (s > n) return 0;
    int sz = v.size();
    v.push_back({n + 1, 0});
    vi erased(sz);
    for (int i = 0; i < sz; i++) {
        auto [x, cnt] = v[i];
        for (int j = i; j < sz && cnt; j++) {
            int count = seg.query(v[j].x, v[j + 1].x, roots[x], 1, n + 1) - erased[j];
            erased[j] += min(count, cnt);
            cnt -= min(count, cnt);
        }
        if (cnt) return 0;
    }
    return 1;
}
//4
//2 4
//1 2
//2 3
//2 3
//2
//2 1 3
//2 1 1

Compilation message

teams.cpp: In member function 'void Seg::Fix(int)':
teams.cpp:27:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   27 |             l[i] = seg.size();
      |                    ~~~~~~~~^~
teams.cpp:29:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   29 |             r[i] = seg.size();
      |                    ~~~~~~~~^~
teams.cpp: In member function 'int Seg::update(int, int, int, int)':
teams.cpp:34:28: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |         int copy = seg.size();
      |                    ~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:98:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   98 |     int sz = v.size();
      |              ~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 316 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 25764 KB Output is correct
2 Correct 112 ms 26776 KB Output is correct
3 Correct 105 ms 26672 KB Output is correct
4 Correct 92 ms 27084 KB Output is correct
5 Correct 71 ms 24368 KB Output is correct
6 Correct 78 ms 24352 KB Output is correct
7 Correct 73 ms 24316 KB Output is correct
8 Correct 69 ms 24328 KB Output is correct
9 Correct 65 ms 24792 KB Output is correct
10 Correct 60 ms 23332 KB Output is correct
11 Correct 66 ms 24456 KB Output is correct
12 Correct 70 ms 24624 KB Output is correct
13 Correct 70 ms 24028 KB Output is correct
14 Correct 76 ms 25952 KB Output is correct
15 Correct 107 ms 26448 KB Output is correct
16 Correct 102 ms 26480 KB Output is correct
17 Correct 71 ms 25256 KB Output is correct
18 Correct 67 ms 25224 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 25844 KB Output is correct
2 Correct 126 ms 27284 KB Output is correct
3 Correct 194 ms 30620 KB Output is correct
4 Correct 107 ms 27124 KB Output is correct
5 Correct 91 ms 24924 KB Output is correct
6 Correct 83 ms 24964 KB Output is correct
7 Correct 91 ms 24948 KB Output is correct
8 Correct 96 ms 25000 KB Output is correct
9 Correct 65 ms 24744 KB Output is correct
10 Correct 65 ms 23728 KB Output is correct
11 Correct 79 ms 25064 KB Output is correct
12 Correct 1039 ms 25332 KB Output is correct
13 Correct 295 ms 25028 KB Output is correct
14 Correct 207 ms 28932 KB Output is correct
15 Correct 129 ms 27164 KB Output is correct
16 Correct 133 ms 27152 KB Output is correct
17 Correct 90 ms 25884 KB Output is correct
18 Correct 93 ms 25920 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 755 ms 142636 KB Output is correct
2 Correct 758 ms 149540 KB Output is correct
3 Correct 1043 ms 154188 KB Output is correct
4 Correct 753 ms 149484 KB Output is correct
5 Correct 513 ms 145752 KB Output is correct
6 Correct 502 ms 145712 KB Output is correct
7 Correct 468 ms 145708 KB Output is correct
8 Correct 485 ms 145804 KB Output is correct
9 Correct 383 ms 146204 KB Output is correct
10 Correct 366 ms 144272 KB Output is correct
11 Correct 1329 ms 144784 KB Output is correct
12 Correct 3269 ms 145436 KB Output is correct
13 Correct 1199 ms 147024 KB Output is correct
14 Correct 1036 ms 149344 KB Output is correct
15 Correct 699 ms 149228 KB Output is correct
16 Correct 654 ms 149284 KB Output is correct
17 Correct 454 ms 148300 KB Output is correct
18 Correct 461 ms 148164 KB Output is correct