oj.uz

Submission #887033

# Submission time Handle Problem Language Result Execution time Memory
887033 2023-12-13T13:57:46 Z abcvuitunggio Teams (IOI15_teams) C++17
100 / 100
 1238 ms 338072 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],pos[500001];
vector <int> v[500001],ve,tmp;
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;
}
void fakeget(int l=1, int r=n, int u=1, int v=ve.size()-1){
    if (u>v||ve[v]<l||ve[u]>r)
        return;
    if (l==r)
        return;
    int mid=(l+r)>>1;
    pos[mid]=upper_bound(ve.begin(),ve.end(),mid)-ve.begin();
    fakeget(l,mid,u,min(v,pos[mid]-1));
    fakeget(mid+1,r,max(pos[mid],u),v);
}
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;
    return max(get(le[node],l,mid,u,min(v,pos[mid]-1)),get(ri[node],mid+1,r,max(pos[mid],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());
    fakeget();
    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,tmp;
      |              ^
teams.cpp: At global scope:
teams.cpp:22:56: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   22 | void fakeget(int l=1, int r=n, int u=1, int v=ve.size()-1){
      |                                               ~~~~~~~~~^~
teams.cpp: In function 'void fakeget(int, int, int, int)':
teams.cpp:22:45: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   22 | void fakeget(int l=1, int r=n, int u=1, int v=ve.size()-1){
      |                                         ~~~~^~~~~~~~~~~~~
teams.cpp:6:14: note: shadowed declaration is here
    6 | vector <int> v[500001],ve,tmp;
      |              ^
teams.cpp:28:50: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   28 |     pos[mid]=upper_bound(ve.begin(),ve.end(),mid)-ve.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:32:44: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   32 | 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,tmp;
      |              ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:67:13: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   67 |     fakeget();
      |             ^
teams.cpp:68:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   68 |     for (int i=ve.size()-1;i>=0;i--)
      |                ~~~~~~~~~^~
teams.cpp:69:51: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   69 |         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 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 4 ms 16984 KB Output is correct
10 Correct 3 ms 17240 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 17004 KB Output is correct
13 Correct 3 ms 16988 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 3 ms 16984 KB Output is correct
16 Correct 3 ms 16988 KB Output is correct
17 Correct 3 ms 16984 KB Output is correct
18 Correct 3 ms 16988 KB Output is correct
19 Correct 3 ms 16988 KB Output is correct
20 Correct 4 ms 16988 KB Output is correct
21 Correct 3 ms 16988 KB Output is correct
22 Correct 4 ms 16988 KB Output is correct
23 Correct 3 ms 16984 KB Output is correct
24 Correct 4 ms 16988 KB Output is correct
25 Correct 4 ms 16988 KB Output is correct
26 Correct 3 ms 16988 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 74324 KB Output is correct
2 Correct 60 ms 74180 KB Output is correct
3 Correct 57 ms 74280 KB Output is correct
4 Correct 58 ms 74576 KB Output is correct
5 Correct 21 ms 42456 KB Output is correct
6 Correct 21 ms 42332 KB Output is correct
7 Correct 21 ms 42328 KB Output is correct
8 Correct 22 ms 42332 KB Output is correct
9 Correct 11 ms 21716 KB Output is correct
10 Correct 19 ms 42196 KB Output is correct
11 Correct 21 ms 42196 KB Output is correct
12 Correct 22 ms 46260 KB Output is correct
13 Correct 36 ms 62804 KB Output is correct
14 Correct 34 ms 42708 KB Output is correct
15 Correct 58 ms 72028 KB Output is correct
16 Correct 55 ms 72028 KB Output is correct
17 Correct 26 ms 50524 KB Output is correct
18 Correct 33 ms 62776 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 74836 KB Output is correct
2 Correct 266 ms 74724 KB Output is correct
3 Correct 133 ms 77580 KB Output is correct
4 Correct 64 ms 74600 KB Output is correct
5 Correct 227 ms 42812 KB Output is correct
6 Correct 224 ms 42852 KB Output is correct
7 Correct 221 ms 42764 KB Output is correct
8 Correct 261 ms 42976 KB Output is correct
9 Correct 9 ms 21712 KB Output is correct
10 Correct 19 ms 42452 KB Output is correct
11 Correct 24 ms 42452 KB Output is correct
12 Correct 197 ms 46640 KB Output is correct
13 Correct 169 ms 63476 KB Output is correct
14 Correct 157 ms 71764 KB Output is correct
15 Correct 101 ms 72448 KB Output is correct
16 Correct 101 ms 72448 KB Output is correct
17 Correct 82 ms 55408 KB Output is correct
18 Correct 80 ms 73424 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1238 ms 331776 KB Output is correct
2 Correct 1234 ms 331480 KB Output is correct
3 Correct 656 ms 338072 KB Output is correct
4 Correct 438 ms 331428 KB Output is correct
5 Correct 952 ms 147572 KB Output is correct
6 Correct 954 ms 147024 KB Output is correct
7 Correct 957 ms 147044 KB Output is correct
8 Correct 959 ms 147100 KB Output is correct
9 Correct 29 ms 34816 KB Output is correct
10 Correct 97 ms 164296 KB Output is correct
11 Correct 202 ms 164304 KB Output is correct
12 Correct 785 ms 189496 KB Output is correct
13 Correct 770 ms 266848 KB Output is correct
14 Correct 741 ms 309532 KB Output is correct
15 Correct 454 ms 317960 KB Output is correct
16 Correct 459 ms 316384 KB Output is correct
17 Correct 277 ms 250888 KB Output is correct
18 Correct 278 ms 259092 KB Output is correct