Submission #887025

#	Time	Username	Problem	Language	Result	Execution time	Memory
887025		abcvuitunggio	Teams (IOI15_teams)	C++17	100 / 100	3409 ms	348416 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23