Submission #484798

#	Time	Username	Problem	Language	Result	Execution time	Memory
484798		couplefire	Teams (IOI15_teams)	C++17	100 / 100	1630 ms	362920 KiB

teams

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 5e5 + 10;
int chosen, pre[N], n, start;
vector<int> t, L, R, kid[N];
 
int newleaf( int va ) {
    t.emplace_back( va );
    L.emplace_back( -1 ), R.emplace_back( -1 );
    return t.size() - 1;
}
 
int newpar( int l, int r ) {
    t.emplace_back( t[l] + t[r] );
    L.emplace_back( l ), R.emplace_back( r );
    return t.size() - 1;
}
 
int build( int l = 0, int r = N-1 ) {
    if( l == r ) return newleaf( 0 );
    int mid = l + r >> 1;
    return newpar( build( l, mid ), build( mid+1, r ) );
}
 
int update( int x, int pv, int l = 0, int r = N-1 ) {
    if( l == r ) return newleaf( t[pv] + 1 );
    int mid = l + r >> 1;
    if( x <= mid ) return newpar( update( x, L[pv], l, mid ), R[pv] );
    else return newpar( L[pv], update( x, R[pv], mid+1, r ) );
}
 
int remove( int x, int pv, int ze, int l = 0, int r = N-1 ) {
    if( r <= x ) return ze;
    if( l > x ) return pv;
    int mid = l + r >> 1;
    return newpar( remove( x, L[pv], L[ze], l, mid ), remove( x, R[pv], R[ze], mid+1, r ) );
}
 
int choose( int k, int all, int cho, int l = 0, int r = N-1 ) {
    if( l == r ) return newleaf( t[cho] + k );
    int sum = t[L[all]] - t[L[cho]];
    int mid = l + r >> 1;
    if( sum < k ) return newpar( L[all], choose( k-sum, R[all], R[cho], mid+1, r ) );
    else return newpar( choose( k, L[all], L[cho], l, mid ), R[cho] );
}
 
int can( int m, int k[] ) {
    sort( k, k+m );
    int chosen = start;
    for( int i = 0 ; i < m ; i++ ) {
        chosen = remove( k[i]-1, chosen, pre[0] );
        if( t[pre[k[i]]] - t[chosen] < k[i] ) return 0;
        chosen = choose( k[i], pre[k[i]], chosen );
    }
    return 1;
}
 
void init( int _n, int a[], int b[] ) {
    n = _n;
    pre[0] = build();
    for( int i = 0 ; i < n ; i++ ) kid[a[i]].emplace_back( b[i] );
    for( int i = 1 ; i <= n ; i++ ) {
        pre[i] = remove( i-1, pre[i-1], pre[0] );
        for( int b : kid[i] ) pre[i] = update( b, pre[i] );
    }
    start = build();
}

Compilation message (stderr)

teams.cpp: In function 'int newleaf(int)':
teams.cpp:12:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   12 |     return t.size() - 1;
      |            ~~~~~~~~~^~~
teams.cpp: In function 'int newpar(int, int)':
teams.cpp:18:21: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   18 |     return t.size() - 1;
      |            ~~~~~~~~~^~~
teams.cpp: In function 'int build(int, int)':
teams.cpp:23:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |     int mid = l + r >> 1;
      |               ~~^~~
teams.cpp: In function 'int update(int, int, int, int)':
teams.cpp:29:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int mid = l + r >> 1;
      |               ~~^~~
teams.cpp: In function 'int remove(int, int, int, int, int)':
teams.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
teams.cpp: In function 'int choose(int, int, int, int, int)':
teams.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:51:9: warning: declaration of 'chosen' shadows a global declaration [-Wshadow]
   51 |     int chosen = start;
      |         ^~~~~~
teams.cpp:6:5: note: shadowed declaration is here
    6 | int chosen, pre[N], n, start;
      |     ^~~~~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:66:18: warning: declaration of 'int b' shadows a parameter [-Wshadow]
   66 |         for( int b : kid[i] ) pre[i] = update( b, pre[i] );
      |                  ^
teams.cpp:60:33: note: shadowed declaration is here
   60 | void init( int _n, int a[], int b[] ) {
      |                             ~~~~^~~

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