oj.uz

Submission #887025

# Submission time Handle Problem Language Result Execution time Memory
887025 2023-12-13T13:41:02 Z abcvuitunggio Teams (IOI15_teams) C++17
100 / 100
 3409 ms 348416 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n,cnt[500001],dp[1010],root[500001],st[40000001],le[40000001],ri[40000001],nNode,nRoot,R[500001];
vector <int> v[500001],ve;
int update(int node, int l, int r, int u, int v){
    int mid=(l+r)>>1,cur=++nNode;
    st[cur]=st[node];
    le[cur]=le[node];
    ri[cur]=ri[node];
    if (l>=u&&r<=v){
        st[cur]++;
        return cur;
    }
    if (u<=mid)
        le[cur]=update(le[node],l,mid,u,v);
    if (v>mid)
        ri[cur]=update(ri[node],mid+1,r,u,v);
    return cur;
}
int get(int node, int l, int r, int u, int v){
    if (u>v||ve[v]<l||ve[u]>r)
        return -INF;
    if (l==r)
        return dp[u]-st[node];
    int mid=(l+r)>>1;
    int x=upper_bound(ve.begin(),ve.end(),mid)-ve.begin();
    return max(get(le[node],l,mid,u,min(v,x-1)),get(ri[node],mid+1,r,max(x,u),v))-st[node];
}
void init(int N, int A[], int B[]){
    n=N;
    for (int i=0;i<n;i++)
        v[A[i]].push_back(B[i]);
    for (int i=n;i;i--){
        for (int j:v[i]){
            nRoot++;
            root[nRoot]=update(root[nRoot-1],1,n,i,j);
        }
        R[i]=root[nRoot];
    }
}
int can(int M, int K[]){
    int sum=0;
    for (int i=0;i<M;i++){
        sum+=K[i];
        cnt[K[i]]=0;
        if (sum>n)
            return 0;
    }
    ve={0};
    for (int i=0;i<M;i++){
        if (!cnt[K[i]])
            ve.push_back(K[i]);
        cnt[K[i]]+=K[i];
    }
    sort(ve.begin(),ve.end());
    for (int i=ve.size()-1;i>=0;i--)
        dp[i]=max(get(R[ve[i]+1],1,n,i+1,ve.size()-1),0)+cnt[ve[i]];
    return (!dp[0]);
}

Compilation message

teams.cpp: In function 'int update(int, int, int, int, int)':
teams.cpp:7:47: warning: declaration of 'v' shadows a global declaration [-Wshadow]
    7 | int update(int node, int l, int r, int u, int v){
      |                                           ~~~~^
teams.cpp:6:14: note: shadowed declaration is here
    6 | vector <int> v[500001],ve;
      |              ^
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:22:44: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   22 | int get(int node, int l, int r, int u, int v){
      |                                        ~~~~^
teams.cpp:6:14: note: shadowed declaration is here
    6 | vector <int> v[500001],ve;
      |              ^
teams.cpp:28:47: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   28 |     int x=upper_bound(ve.begin(),ve.end(),mid)-ve.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:58:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |     for (int i=ve.size()-1;i>=0;i--)
      |                ~~~~~~~~~^~
teams.cpp:59:51: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   59 |         dp[i]=max(get(R[ve[i]+1],1,n,i+1,ve.size()-1),0)+cnt[ve[i]];
      |                                          ~~~~~~~~~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 72004 KB Output is correct
2 Correct 61 ms 71864 KB Output is correct
3 Correct 60 ms 72020 KB Output is correct
4 Correct 59 ms 72272 KB Output is correct
5 Correct 22 ms 40028 KB Output is correct
6 Correct 22 ms 40176 KB Output is correct
7 Correct 22 ms 40024 KB Output is correct
8 Correct 22 ms 40172 KB Output is correct
9 Correct 9 ms 19668 KB Output is correct
10 Correct 19 ms 39916 KB Output is correct
11 Correct 20 ms 41936 KB Output is correct
12 Correct 22 ms 43988 KB Output is correct
13 Correct 34 ms 60572 KB Output is correct
14 Correct 25 ms 40332 KB Output is correct
15 Correct 55 ms 71640 KB Output is correct
16 Correct 52 ms 69712 KB Output is correct
17 Correct 28 ms 48276 KB Output is correct
18 Correct 31 ms 60500 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 72252 KB Output is correct
2 Correct 550 ms 72532 KB Output is correct
3 Correct 110 ms 75344 KB Output is correct
4 Correct 60 ms 72272 KB Output is correct
5 Correct 473 ms 40672 KB Output is correct
6 Correct 523 ms 40960 KB Output is correct
7 Correct 455 ms 40316 KB Output is correct
8 Correct 504 ms 40320 KB Output is correct
9 Correct 8 ms 19664 KB Output is correct
10 Correct 19 ms 40144 KB Output is correct
11 Correct 26 ms 42196 KB Output is correct
12 Correct 476 ms 44476 KB Output is correct
13 Correct 194 ms 61136 KB Output is correct
14 Correct 144 ms 69456 KB Output is correct
15 Correct 127 ms 70332 KB Output is correct
16 Correct 119 ms 70200 KB Output is correct
17 Correct 130 ms 52656 KB Output is correct
18 Correct 114 ms 70908 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2926 ms 333648 KB Output is correct
2 Correct 3409 ms 333532 KB Output is correct
3 Correct 564 ms 348416 KB Output is correct
4 Correct 403 ms 340328 KB Output is correct
5 Correct 2609 ms 149416 KB Output is correct
6 Correct 3120 ms 149584 KB Output is correct
7 Correct 2634 ms 149440 KB Output is correct
8 Correct 3088 ms 149388 KB Output is correct
9 Correct 32 ms 37312 KB Output is correct
10 Correct 97 ms 164972 KB Output is correct
11 Correct 342 ms 165760 KB Output is correct
12 Correct 1934 ms 191596 KB Output is correct
13 Correct 811 ms 270424 KB Output is correct
14 Correct 672 ms 318920 KB Output is correct
15 Correct 519 ms 326848 KB Output is correct
16 Correct 522 ms 324708 KB Output is correct
17 Correct 412 ms 255344 KB Output is correct
18 Correct 395 ms 263352 KB Output is correct