Submission #541128

#	Time	Username	Problem	Language	Result	Execution time	Memory
541128		lukameladze	Teams (IOI15_teams)	C++14	21 / 100	4085 ms	38448 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int tree[10*N],le_[10*N], ri_[10*N];
int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
vector <int> v[N];
int merge(int a, int b) {
    return a + b;
}
void build(int node, int le, int ri) {
   // cout<<le<<" "<<ri<<" "<<node<<endl;
    if (le == ri) {
        tree[node] = 0;
        return ;
    }
    cur++;
    le_[node] = cur;
    cur++;
    ri_[node] = cur;
    int mid = (le + ri) / 2;
    build(le_[node],le,mid);
    build(ri_[node],mid + 1, ri);
    tree[node] = merge(tree[le_[node]], tree[ri_[node]]);
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    
    if (le == ri) {
        //cout<<cur<<" "<<val<<endl;
        
        tree[cur] = tree[node] + val;
        //cout<<cur<<" "<<le<<" "<<ri<<" "<<tree[cur]<<endl;
        return ;
    }
    int mid = (le + ri) / 2;
    int x = cur;
    cur++;
    le_[x] = le_[node];
    ri_[x] = ri_[node];
    if (idx <= mid) {
        le_[x] = cur;
    } else ri_[x] = cur;
    update(le_[node], le,mid,idx,val);
    update(ri_[node], mid + 1, ri, idx,val);
    tree[x] = merge(tree[le_[x]], tree[ri_[x]]);
    //cout<<x<<" "<<le<<" "<<ri<<" "<<tree[x]<<endl;
}
int getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) {
        return tree[node];
    }
    int mid = (le + ri) / 2;
    return merge(getans(le_[node],le,mid,start,end), getans(ri_[node],mid + 1,ri,start,end));
}
int can(int M, int K[]) {
	m = M;
	for (int i = 1; i <= m; i++) {
		dp[i] = 1e9;
		k[i] = K[i - 1];
	}
	int sum = 0;
    for (int i = 1; i <= m; i++) {
        sum += k[i];
    }
    if (sum > n) {
        return 0;
    }
    sort(k + 1, k + m + 1);
	dp[0] = 0;
	 for (int i = 1; i <= m; i++) {
        for (int j = i - 1; j >= 0; j--) {
            // k[j]+1 -----> k[i] shualedshi >= k[i] 
            cnt = getans(root[k[i]],1,n,k[i],n) - getans(root[k[j]],1,n,k[i],n);
            dp[i] = min(dp[i],dp[j] + cnt - k[i]);
            //cout<<i<<" "<<j<<" "<<dp[j]<<" "<<cnt<<endl;
            if (dp[i] < 0) {
                return 0;
            }
        }
        //cout<<i<<" "<<dp[i]<<endl;
    }
    return 1;
}
void init(int N, int A[], int B[]) {
	n = N;
    for (int i = 1; i <= n; i++) {
        a[i] = A[i - 1]; b[i] = B[i - 1];
        v[a[i]].pb(b[i]);
    }
    
    cur = 1; root[0] = 1;
    build(1,1,n); 
    for (int i = 1; i <= n; i++) {
        prevroot = root[i - 1];
        root[i] = root[i - 1];
        for (int j = 0; j < v[i].size(); j++) {
            cur++;
            root[i] = cur;
            update(prevroot, 1,n,v[i][j],1);
            prevroot = root[i];
        }
    }
    dp[0] = 0;
   
}

Compilation message (stderr)

teams.cpp: In function 'int merge(int, int)':
teams.cpp:11:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   11 | int merge(int a, int b) {
      |                  ~~~~^
teams.cpp:9:39: note: shadowed declaration is here
    9 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                       ^
teams.cpp:11:15: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   11 | int merge(int a, int b) {
      |           ~~~~^
teams.cpp:9:34: note: shadowed declaration is here
    9 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                  ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:89:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   89 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:7:11: note: shadowed declaration is here
    7 | const int N = 3e5 + 5;
      |           ^
teams.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

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