oj.uz

답안 #671029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671029 2022-12-11T17:11:32 Z LittleCube 팀들 (IOI15_teams) C++17
100 / 100
 1077 ms 288776 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

int N, root[500005];
vector<int> v[500005];
struct node
{
    int t = 0, l = -1, r = -1, val = 0;
};
vector<node> pSeg(1);

int copy_node(int i, int t)
{
    int j = pSeg.size();
    pSeg.emplace_back(pSeg[i]);
    pSeg[j].t = t;
    return j;
}

void build(int i, int L = 1, int R = N)
{
    if (L != R)
    {
        int mid = (L + R) / 2;
        pSeg[i].l = pSeg.size();
        pSeg.emplace_back(node{});
        build(pSeg[i].l, L, mid);
        pSeg[i].r = pSeg.size();
        pSeg.emplace_back(node{});
        build(pSeg[i].r, mid + 1, R);
    }
}

void modify(int pos, int i, int L = 1, int R = N)
{
    if (L != R)
    {
        int mid = (L + R) / 2;
        if (pos <= mid)
        {
            if (pSeg[pSeg[i].l].t < pSeg[i].t)
                pSeg[i].l = copy_node(pSeg[i].l, pSeg[i].t);
            modify(pos, pSeg[i].l, L, mid);
        }
        else
        {
            if (pSeg[pSeg[i].r].t < pSeg[i].t)
                pSeg[i].r = copy_node(pSeg[i].r, pSeg[i].t);
            modify(pos, pSeg[i].r, mid + 1, R);
        }
        pSeg[i].val = pSeg[pSeg[i].l].val + pSeg[pSeg[i].r].val;
    }
    else
        pSeg[i].val++;
}

int query(int qL, int qR, int i, int L = 1, int R = N)
{
    if (qL <= L && R <= qR)
        return pSeg[i].val;
    else if (R < qL || qR < L)
        return 0;
    else
    {
        int mid = (L + R) / 2;
        return query(qL, qR, pSeg[i].l, L, mid) + query(qL, qR, pSeg[i].r, mid + 1, R);
    }
}

void init(int n, int A[], int B[])
{
    N = n;
    for (int i = 0; i < N; i++)
        v[A[i]].emplace_back(B[i]);
    root[0] = 0;
    build(0);
    for (int i = 1; i <= N; i++)
    {
        root[i] = copy_node(root[i - 1], i);
        for (int j : v[i])
            modify(j, root[i]);
    }
}

//                                L              R
// dp[i] = min dp[j] + n([K[j] + 1, K[i]] x [K[i], N]) - cnt
// Segment tree should maintain R, and binary search cost through two version of L (K[i] and K[j])
int can(int M, int k[])
{
    sort(k, k + M);
    vector<int> K(1, 0), cnt(1, 0);
    for (int i = 0; i < M; i++)
        if (k[i] == K.back())
            cnt.back() += k[i];
        else
        {
            K.emplace_back(k[i]);
            cnt.emplace_back(k[i]);
        }
    M = (int)K.size() - 1;
    vector<int> dp(K.size(), 0);
    for (int i = 1; i <= M; i++)
    {
        dp[i] = 1e8;
        for (int j = max(0, i - 25); j < i; j++)
        {
            dp[i] = min(dp[i], dp[j] + query(K[i], N, root[K[i]]) - query(K[i], N, root[K[j]]) - cnt[i]);
        }
        if (dp[i] < 0)
            return 0;
    }
    return 1;
}

Compilation message

teams.cpp: In function 'int copy_node(int, int)':
teams.cpp:18:22: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   18 |     int j = pSeg.size();
      |             ~~~~~~~~~^~
teams.cpp: In function 'void build(int, int, int)':
teams.cpp:29:30: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |         pSeg[i].l = pSeg.size();
      |                     ~~~~~~~~~^~
teams.cpp:32:30: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   32 |         pSeg[i].r = pSeg.size();
      |                     ~~~~~~~~~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 47616 KB Output is correct
2 Correct 89 ms 47624 KB Output is correct
3 Correct 110 ms 47656 KB Output is correct
4 Correct 94 ms 47696 KB Output is correct
5 Correct 31 ms 21984 KB Output is correct
6 Correct 31 ms 21992 KB Output is correct
7 Correct 29 ms 22060 KB Output is correct
8 Correct 30 ms 22016 KB Output is correct
9 Correct 28 ms 21756 KB Output is correct
10 Correct 29 ms 21756 KB Output is correct
11 Correct 29 ms 21704 KB Output is correct
12 Correct 31 ms 21692 KB Output is correct
13 Correct 39 ms 30436 KB Output is correct
14 Correct 49 ms 30516 KB Output is correct
15 Correct 83 ms 47560 KB Output is correct
16 Correct 79 ms 47568 KB Output is correct
17 Correct 32 ms 21816 KB Output is correct
18 Correct 35 ms 21872 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 47688 KB Output is correct
2 Correct 95 ms 47760 KB Output is correct
3 Correct 212 ms 47920 KB Output is correct
4 Correct 93 ms 47656 KB Output is correct
5 Correct 437 ms 22084 KB Output is correct
6 Correct 396 ms 22072 KB Output is correct
7 Correct 36 ms 22048 KB Output is correct
8 Correct 291 ms 22036 KB Output is correct
9 Correct 29 ms 21848 KB Output is correct
10 Correct 32 ms 21764 KB Output is correct
11 Correct 50 ms 21752 KB Output is correct
12 Correct 377 ms 21708 KB Output is correct
13 Correct 262 ms 30388 KB Output is correct
14 Correct 219 ms 47448 KB Output is correct
15 Correct 158 ms 47624 KB Output is correct
16 Correct 161 ms 47512 KB Output is correct
17 Correct 165 ms 21796 KB Output is correct
18 Correct 135 ms 21848 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 637 ms 288740 KB Output is correct
2 Correct 643 ms 288776 KB Output is correct
3 Correct 988 ms 288684 KB Output is correct
4 Correct 614 ms 288756 KB Output is correct
5 Correct 1077 ms 52048 KB Output is correct
6 Correct 927 ms 52096 KB Output is correct
7 Correct 137 ms 51988 KB Output is correct
8 Correct 791 ms 52112 KB Output is correct
9 Correct 124 ms 51020 KB Output is correct
10 Correct 128 ms 51020 KB Output is correct
11 Correct 371 ms 51020 KB Output is correct
12 Correct 1018 ms 51044 KB Output is correct
13 Correct 839 ms 85488 KB Output is correct
14 Correct 971 ms 287488 KB Output is correct
15 Correct 670 ms 155536 KB Output is correct
16 Correct 677 ms 155464 KB Output is correct
17 Correct 442 ms 51420 KB Output is correct
18 Correct 425 ms 51772 KB Output is correct