oj.uz

답안 #671122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671122 2022-12-12T05:25:49 Z LittleCube 팀들 (IOI15_teams) C++17
100 / 100
 952 ms 290148 KB 
#include "teams.h"
#pragma GCC optimize("Ofast,unroll-loops")
#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 - 10); 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:19:22: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   19 |     int j = pSeg.size();
      |             ~~~~~~~~~^~
teams.cpp: In function 'void build(int, int, int)':
teams.cpp:30:30: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   30 |         pSeg[i].l = pSeg.size();
      |                     ~~~~~~~~~^~
teams.cpp:33:30: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   33 |         pSeg[i].r = pSeg.size();
      |                     ~~~~~~~~~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 47632 KB Output is correct
2 Correct 83 ms 48032 KB Output is correct
3 Correct 86 ms 47960 KB Output is correct
4 Correct 90 ms 47936 KB Output is correct
5 Correct 32 ms 22336 KB Output is correct
6 Correct 29 ms 22328 KB Output is correct
7 Correct 30 ms 22352 KB Output is correct
8 Correct 31 ms 22368 KB Output is correct
9 Correct 29 ms 22136 KB Output is correct
10 Correct 27 ms 22116 KB Output is correct
11 Correct 29 ms 22068 KB Output is correct
12 Correct 30 ms 22012 KB Output is correct
13 Correct 41 ms 30728 KB Output is correct
14 Correct 45 ms 30844 KB Output is correct
15 Correct 80 ms 47920 KB Output is correct
16 Correct 73 ms 47888 KB Output is correct
17 Correct 32 ms 22124 KB Output is correct
18 Correct 33 ms 22124 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 47652 KB Output is correct
2 Correct 92 ms 48140 KB Output is correct
3 Correct 186 ms 48496 KB Output is correct
4 Correct 89 ms 48304 KB Output is correct
5 Correct 185 ms 22380 KB Output is correct
6 Correct 165 ms 22252 KB Output is correct
7 Correct 37 ms 22336 KB Output is correct
8 Correct 141 ms 22224 KB Output is correct
9 Correct 28 ms 22200 KB Output is correct
10 Correct 31 ms 22016 KB Output is correct
11 Correct 43 ms 22068 KB Output is correct
12 Correct 172 ms 21940 KB Output is correct
13 Correct 199 ms 30880 KB Output is correct
14 Correct 226 ms 47812 KB Output is correct
15 Correct 155 ms 48068 KB Output is correct
16 Correct 157 ms 48064 KB Output is correct
17 Correct 117 ms 22324 KB Output is correct
18 Correct 100 ms 22272 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 641 ms 288708 KB Output is correct
2 Correct 655 ms 289944 KB Output is correct
3 Correct 952 ms 289960 KB Output is correct
4 Correct 623 ms 290148 KB Output is correct
5 Correct 490 ms 53544 KB Output is correct
6 Correct 453 ms 53520 KB Output is correct
7 Correct 153 ms 53520 KB Output is correct
8 Correct 387 ms 53176 KB Output is correct
9 Correct 121 ms 52296 KB Output is correct
10 Correct 127 ms 52196 KB Output is correct
11 Correct 214 ms 52012 KB Output is correct
12 Correct 508 ms 52256 KB Output is correct
13 Correct 672 ms 86632 KB Output is correct
14 Correct 940 ms 288576 KB Output is correct
15 Correct 636 ms 156696 KB Output is correct
16 Correct 614 ms 156596 KB Output is correct
17 Correct 322 ms 52624 KB Output is correct
18 Correct 322 ms 53012 KB Output is correct