Submission #550972

#	Time	Username	Problem	Language	Result	Execution time	Memory
550972		elazarkoren	Teams (IOI15_teams)	C++17	100 / 100	3269 ms	154188 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23