oj.uz

Submission #607407

# Submission time Handle Problem Language Result Execution time Memory
607407 2022-07-26T16:38:13 Z yuto1115 Teams (IOI15_teams) C++17
77 / 100
 2803 ms 524288 KB 
#include "teams.h"
#include "bits/stdc++.h"
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

class segtree {
    struct node {
        ll lrd;
        node *cl;
        node *cr;
        
        node(int l, int r, int d) : lrd((ll(l) << 40) + (ll(r) << 20) + d), cl(nullptr), cr(nullptr) {}
    };
    
    int n;
    node *root;
    
    node *build(int l, int r, const vi::iterator &a, const vi::iterator &b) {
        if (a == b) return nullptr;
        node *res = new node(l, r, b - a);
        if (r - l > 1) {
            int m = (l + r) / 2;
            auto c = lower_bound(a, b, m);
            res->cl = build(l, m, a, c);
            res->cr = build(m, r, c, b);
        }
        return res;
    }
    
    int count(int l, int r, node *nd) {
        if (nd == nullptr) return 0;
        int nl = nd->lrd >> 40;
        int nr = (nd->lrd >> 20) - (nl << 20);
        if (r <= nl or nr <= l) return 0;
        if (l <= nl and nr <= r) return nd->lrd - (nd->lrd >> 20 << 20);
        return count(l, r, nd->cl) + count(l, r, nd->cr);
    }

public:
    segtree(int _n, const vi::iterator &a, const vi::iterator &b) : n(_n) {
        root = build(0, n, a, b);
    }
    
    int count(int l, int r) {
        assert(0 <= l and l <= r and r <= n);
        return count(l, r, root);
    }
};

vector<segtree> st;

int sz = 1;

void merge(vi &v, const vi &a, const vi &b) {
    int ai = 0, bi = 0;
    v.reserve(SZ(a) + SZ(b));
    while (ai < SZ(a) or bi < SZ(b)) {
        if (ai < SZ(a) and bi < SZ(b)) {
            if (a[ai] < b[bi]) v.pb(a[ai++]);
            else v.pb(b[bi++]);
        } else if (ai < SZ(a)) {
            v.pb(a[ai++]);
        } else {
            v.pb(b[bi++]);
        }
    }
}

void build(const vvi &v) {
    vvi ls(2 * sz);
    rep(i, sz) ls[sz + i] = v[i];
    for (int i = sz - 1; i >= 1; --i) {
        merge(ls[i], ls[2 * i], ls[2 * i + 1]);
    }
    rep(i, 2 * sz) st.eb(sz, all(ls[i]));
}

int n;
vi a, b;

int count(int xl, int xr, int yl, int yr) {
    assert(0 <= xl and xl <= xr and xr <= sz);
    assert(0 <= yl and yl <= yr and yr <= sz);
//    cerr << xl << ' ' << xr << ' ' << yl << ' ' << yr << ' ';
    yl += sz, yr += sz;
    int res = 0;
    while (yl < yr) {
        if (yl & 1) res += st[yl++].count(xl, xr);
        if (yr & 1) res += st[--yr].count(xl, xr);
        yl >>= 1, yr >>= 1;
    }
//    cerr << res << endl;
//    int res = 0;
//    rep(i, n) if (xl <= a[i] and a[i] < xr and yl <= b[i] and b[i] < yr) ++res;
    return res;
}

void init(int N, int A[], int B[]) {
    n = N;
    a = vi(A, A + N);
    b = vi(B, B + N);
    for (int &i: b) ++i;
    while (sz <= n + 1) sz *= 2;
    vvi v(sz);
    rep(i, n) v[b[i]].pb(a[i]);
    rep(i, sz) sort(all(v[i]));
    build(v);
//    cerr << "init : " << N << endl;
}

int max_yr(int xl, int xr, int yl, int ub) {
    assert(0 <= xl and xl <= xr and xr <= sz);
    assert(0 <= yl and yl <= sz);
    assert(ub > 0);
    yl += sz;
    while (true) {
        if ((yl & -yl) == yl) return sz;
        while (~yl & 1) yl >>= 1;
        int now = st[yl].count(xl, xr);
        if (now < ub) {
            ub -= now;
            ++yl;
            continue;
        }
        while (yl < sz) {
            yl *= 2;
            now = st[yl].count(xl, xr);
            if (now < ub) {
                ub -= now;
                ++yl;
            }
        }
        return yl - sz;
    }
}

int can(int m, int K[]) {
    vi k = vi(K, K + m);
    sort(all(k));
    // {x, max_y, rem in max_y}
    vvi v;
    v.pb({0, n + 1, 0});
    for (int i: k) {
//        cerr << "i : " << i << endl;
//        for (auto t: v) cerr << "v : " << t[0] << ' ' << t[1] << ' ' << t[2] << endl;
        while (v.back()[1] < i + 1) v.pop_back();
        int now = i + 1;
        int rem = i;
        while (true) {
            if (now > n + 1) return 0;
            assert(v.back()[1] >= now);
            int sum = count(v.back()[0] + 1, i + 1, now, v.back()[1] + 1) + v.back()[2];
            if (sum < rem) {
                rem -= sum;
                now = v.back()[1] + 1;
                v.pop_back();
                continue;
            }
            int psum = count(v.back()[0] + 1, i + 1, now, v.back()[1]);
            if (psum < rem) {
                v.back()[0] = i;
                v.back()[2] = sum - rem;
            } else {
                int ok = max_yr(v.back()[0] + 1, i + 1, now, rem) + 1;
                v.eb(vi{i, ok - 1, count(v.back()[0] + 1, i + 1, now, ok) - rem});
            }
            break;
        }
    }
//    cerr << "i : end" << endl;
//    for (auto t: v) cerr << "v : " << t[0] << ' ' << t[1] << ' ' << t[2] << endl;
    return 1;
}

Compilation message

teams.cpp: In member function 'segtree::node* segtree::build(int, int, const iterator&, const iterator&)':
teams.cpp:57:38: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   57 |         node *res = new node(l, r, b - a);
      |                                    ~~^~~
teams.cpp: In member function 'int segtree::count(int, int, segtree::node*)':
teams.cpp:69:26: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |         int nl = nd->lrd >> 40;
      |                  ~~~~~~~~^~~~~
teams.cpp:70:34: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   70 |         int nr = (nd->lrd >> 20) - (nl << 20);
      |                  ~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 506120 KB Output is correct
2 Correct 779 ms 506264 KB Output is correct
3 Correct 903 ms 506200 KB Output is correct
4 Correct 974 ms 506244 KB Output is correct
5 Correct 35 ms 23868 KB Output is correct
6 Correct 27 ms 24040 KB Output is correct
7 Correct 34 ms 23916 KB Output is correct
8 Correct 29 ms 23868 KB Output is correct
9 Correct 43 ms 22908 KB Output is correct
10 Correct 30 ms 22940 KB Output is correct
11 Correct 28 ms 22908 KB Output is correct
12 Correct 27 ms 24228 KB Output is correct
13 Correct 80 ms 53776 KB Output is correct
14 Correct 250 ms 133980 KB Output is correct
15 Correct 701 ms 422976 KB Output is correct
16 Correct 666 ms 423040 KB Output is correct
17 Correct 58 ms 40632 KB Output is correct
18 Correct 58 ms 40636 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 506060 KB Output is correct
2 Correct 822 ms 506192 KB Output is correct
3 Correct 2366 ms 506232 KB Output is correct
4 Correct 925 ms 507440 KB Output is correct
5 Correct 159 ms 24820 KB Output is correct
6 Correct 132 ms 24840 KB Output is correct
7 Correct 43 ms 24852 KB Output is correct
8 Correct 130 ms 24836 KB Output is correct
9 Correct 37 ms 23624 KB Output is correct
10 Correct 40 ms 23384 KB Output is correct
11 Correct 41 ms 23540 KB Output is correct
12 Correct 137 ms 25016 KB Output is correct
13 Correct 846 ms 55068 KB Output is correct
14 Correct 2803 ms 429712 KB Output is correct
15 Correct 785 ms 423976 KB Output is correct
16 Correct 775 ms 423748 KB Output is correct
17 Correct 173 ms 41556 KB Output is correct
18 Correct 148 ms 41544 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 913 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -