제출 #887023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887023		abcvuitunggio	팀들 (IOI15_teams)	C++17	13 / 100	4035 ms	333216 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 (ve[v]<l||ve[u]>r)
        return -INF;
    int x=lower_bound(ve.begin(),ve.end(),l)-ve.begin(),y=upper_bound(ve.begin(),ve.end(),r)-ve.begin()-1;
    if (x>y)
        return -INF;
    if (l==r)
        return dp[x]-st[node];
    int mid=(l+r)>>1;
    return max(get(le[node],l,mid,u,v),get(ri[node],mid+1,r,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]);
}

컴파일 시 표준 에러 (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:25:45: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   25 |     int x=lower_bound(ve.begin(),ve.end(),l)-ve.begin(),y=upper_bound(ve.begin(),ve.end(),r)-ve.begin()-1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:25:104: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   25 |     int x=lower_bound(ve.begin(),ve.end(),l)-ve.begin(),y=upper_bound(ve.begin(),ve.end(),r)-ve.begin()-1;
      |                                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:60:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   60 |     for (int i=ve.size()-1;i>=0;i--)
      |                ~~~~~~~~~^~
teams.cpp:61:51: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   61 |         dp[i]=max(get(R[ve[i]+1],1,n,i+1,ve.size()-1),0)+cnt[ve[i]];
      |                                          ~~~~~~~~~^~

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