Submission #886979

#	Time	Username	Problem	Language	Result	Execution time	Memory
886979		abcvuitunggio	Teams (IOI15_teams)	C++17	77 / 100	4042 ms	333128 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
int n,cnt[500001],dp[1010],root[500001],st[40000001],le[40000001],ri[40000001],nNode,nRoot,R[500001];
vector <int> v[500001];
int update(int node, int l, int r, int u, int v){
    if (l>=u&&r<=v){
        nNode++;
        st[nNode]=st[node]+1;
        le[nNode]=le[node];
        ri[nNode]=ri[node];
        return nNode;
    }
    int mid=(l+r)>>1,cur=++nNode;
    st[cur]=st[node];
    le[cur]=le[node];
    ri[cur]=ri[node];
    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 x){
    if (l>x||r<x)
        return 0;
    if (l==r)
        return st[node];
    int mid=(l+r)>>1;
    return get(le[node],l,mid,x)+get(ri[node],mid+1,r,x)+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];
        if (sum>n)
            return 0;
    }
    vector <int> ve;
    for (int i=0;i<M;i++){
        cnt[K[i]]++;
        if (cnt[K[i]]==1)
            ve.push_back(K[i]);
    }
    ve.push_back(0);
    sort(ve.begin(),ve.end());
    for (int i=ve.size()-1;i>=0;i--){
        dp[i]=0;
        for (int j=i+1;j<ve.size();j++)
            dp[i]=max(dp[i],dp[j]+ve[j]*cnt[ve[j]]-get(R[ve[i]+1],1,n,ve[j]));
    }
    for (int i=0;i<M;i++)
        cnt[K[i]]=0;
    return (!dp[0]);
}

Compilation message (stderr)

teams.cpp: In function 'int update(int, int, int, int, int)':
teams.cpp:6:47: warning: declaration of 'v' shadows a global declaration [-Wshadow]
    6 | int update(int node, int l, int r, int u, int v){
      |                                           ~~~~^
teams.cpp:5:14: note: shadowed declaration is here
    5 | vector <int> v[500001];
      |              ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:59:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   59 |     for (int i=ve.size()-1;i>=0;i--){
      |                ~~~~~~~~~^~
teams.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int j=i+1;j<ve.size();j++)
      |                        ~^~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23