oj.uz

답안 #929013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
929013 2024-02-17T13:27:13 Z GrindMachine 팀들 (IOI15_teams) C++17
77 / 100
 2859 ms 23820 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 = 1e5 + 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1368 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 1 ms 1116 KB Output is correct
18 Correct 1 ms 1116 KB Output is correct
19 Correct 1 ms 1116 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1116 KB Output is correct
23 Correct 1 ms 1116 KB Output is correct
24 Correct 1 ms 1116 KB Output is correct
25 Correct 1 ms 1116 KB Output is correct
26 Correct 1 ms 1116 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 22552 KB Output is correct
2 Correct 50 ms 22516 KB Output is correct
3 Correct 47 ms 22884 KB Output is correct
4 Correct 52 ms 22548 KB Output is correct
5 Correct 27 ms 17180 KB Output is correct
6 Correct 21 ms 17436 KB Output is correct
7 Correct 26 ms 17176 KB Output is correct
8 Correct 27 ms 17392 KB Output is correct
9 Correct 13 ms 16460 KB Output is correct
10 Correct 17 ms 16568 KB Output is correct
11 Correct 14 ms 16464 KB Output is correct
12 Correct 17 ms 16664 KB Output is correct
13 Correct 21 ms 17932 KB Output is correct
14 Correct 28 ms 19520 KB Output is correct
15 Correct 39 ms 22232 KB Output is correct
16 Correct 38 ms 22224 KB Output is correct
17 Correct 18 ms 17428 KB Output is correct
18 Correct 18 ms 18556 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1841 ms 22564 KB Output is correct
2 Correct 1678 ms 22552 KB Output is correct
3 Correct 159 ms 22544 KB Output is correct
4 Correct 47 ms 23820 KB Output is correct
5 Correct 2859 ms 18204 KB Output is correct
6 Correct 2406 ms 18456 KB Output is correct
7 Correct 2817 ms 18192 KB Output is correct
8 Correct 2444 ms 18452 KB Output is correct
9 Correct 14 ms 17736 KB Output is correct
10 Correct 15 ms 17228 KB Output is correct
11 Correct 35 ms 17232 KB Output is correct
12 Correct 1056 ms 17512 KB Output is correct
13 Correct 406 ms 19232 KB Output is correct
14 Correct 182 ms 23480 KB Output is correct
15 Correct 104 ms 23320 KB Output is correct
16 Correct 124 ms 23308 KB Output is correct
17 Correct 124 ms 18632 KB Output is correct
18 Correct 97 ms 18808 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 10068 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -