oj.uz

Submission #929015

# Submission time Handle Problem Language Result Execution time Memory
929015 2024-02-17T13:28:02 Z GrindMachine Teams (IOI15_teams) C++17
77 / 100
 4000 ms 116168 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

*/

const int MOD = 1e9 + 7;
const int N = 5e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "teams.h"

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        vector<int> a;
    };

    data neutral = {};

    data merge(data &left, data &right) {
        data curr;

        auto &a = left.a, &b = right.a, &c = curr.a;
        int ptr1 = 0, ptr2 = 0;
        while(ptr1 < sz(a) and ptr2 < sz(b)){
            if(a[ptr1] < b[ptr2]){
                c.pb(a[ptr1++]);
            }
            else{
                c.pb(b[ptr2++]);
            }
        }
        while(ptr1 < sz(a)) c.pb(a[ptr1++]);
        while(ptr2 < sz(b)) c.pb(b[ptr2++]);

        return curr;
    }

    void create(int i, T v) {
        tr[i].a = v;
        sort(all(tr[i].a));
    }

    void modify(int i, T v) {

    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    int query(int l, int r, int mn) {
        int res = 0;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            // if (l & 1) resl = merge(resl, tr[l++]);
            // if (!(r & 1)) resr = merge(tr[r--], resr);
            if(l&1){
                auto &v = tr[l++].a;
                res += v.end()-lower_bound(all(v),mn);
            }

            if(!(r&1)){
                auto &v = tr[r--].a;
                res += v.end()-lower_bound(all(v),mn);
            }
        }

        return res;
    }
};

int n;
vector<int> a(N);
vector<int> b(N);
segtree<vector<int>> st;

void init(int n_, int A[], int B[]) {
    n = n_;
    rep(i,n) a[i] = A[i], b[i] = B[i];

    vector<vector<int>> here(n+1);
    rep(i,n) here[a[i]].pb(b[i]);

    st = segtree<vector<int>>(n+1);
    st.build(here,n+1);
}

int can(int m, int K[]) {
    int sum = 0;
    rep(i,m){
        sum += K[i];
        if(sum > n){
            return 0;
        }
    }

    sort(K,K+m);
    vector<pii> c;
    c.pb({K[0],K[0]});
    rep1(i,m-1){
        if(K[i] == K[i-1]){
            c.back().ss += K[i];
        }
        else{
            c.pb({K[i],K[i]});
        }
    }

    auto get = [&](int mnl, int mxl, int mnr){
        return st.query(mnl,mxl,mnr);

        // int cnt = 0;
        // rep(i,n){
        //     if(a[i] >= mnl and a[i] <= mxl and b[i] >= mnr){
        //         cnt++;
        //     }
        // }
        // return cnt;
    };

    c.insert(c.begin(),{0,0});
    m = sz(c);
    vector<int> dp(m,inf1);
    dp[0] = 0;

    rep1(i,m-1){
        rep(j,i){
            amin(dp[i],dp[j]+get(c[j].ff+1,c[i].ff,c[i].ff));
        }

        dp[i] -= c[i].ss;
    }

    int mn = *min_element(all(dp));
    return mn >= 0;
}

Compilation message

teams.cpp: In instantiation of 'int segtree<T>::query(int, int, int) [with T = std::vector<int>]':
teams.cpp:190:36:   required from here
teams.cpp:139:21: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  139 |                 res += v.end()-lower_bound(all(v),mn);
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:144:21: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  144 |                 res += v.end()-lower_bound(all(v),mn);
      |                 ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 25624 KB Output is correct
2 Correct 51 ms 25520 KB Output is correct
3 Correct 43 ms 25612 KB Output is correct
4 Correct 46 ms 25616 KB Output is correct
5 Correct 33 ms 20512 KB Output is correct
6 Correct 27 ms 20508 KB Output is correct
7 Correct 28 ms 20508 KB Output is correct
8 Correct 28 ms 20508 KB Output is correct
9 Correct 15 ms 19528 KB Output is correct
10 Correct 14 ms 19668 KB Output is correct
11 Correct 14 ms 19776 KB Output is correct
12 Correct 22 ms 19804 KB Output is correct
13 Correct 23 ms 20996 KB Output is correct
14 Correct 29 ms 22580 KB Output is correct
15 Correct 44 ms 25276 KB Output is correct
16 Correct 40 ms 25140 KB Output is correct
17 Correct 18 ms 20500 KB Output is correct
18 Correct 18 ms 20628 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1835 ms 25620 KB Output is correct
2 Correct 1698 ms 25616 KB Output is correct
3 Correct 171 ms 25612 KB Output is correct
4 Correct 45 ms 25616 KB Output is correct
5 Correct 2794 ms 20508 KB Output is correct
6 Correct 2468 ms 20376 KB Output is correct
7 Correct 2801 ms 20504 KB Output is correct
8 Correct 2443 ms 20508 KB Output is correct
9 Correct 16 ms 19532 KB Output is correct
10 Correct 18 ms 19532 KB Output is correct
11 Correct 37 ms 19788 KB Output is correct
12 Correct 1070 ms 19820 KB Output is correct
13 Correct 391 ms 21008 KB Output is correct
14 Correct 186 ms 25568 KB Output is correct
15 Correct 104 ms 25292 KB Output is correct
16 Correct 108 ms 25152 KB Output is correct
17 Correct 122 ms 20712 KB Output is correct
18 Correct 104 ms 20600 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4022 ms 116168 KB Time limit exceeded
2 Halted 0 ms 0 KB -