oj.uz

답안 #484798

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484798 2021-11-05T14:09:21 Z couplefire 팀들 (IOI15_teams) C++17
100 / 100
 1630 ms 362920 KB 
#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

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.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 35584 KB Output is correct
2 Correct 36 ms 35680 KB Output is correct
3 Correct 38 ms 35764 KB Output is correct
4 Correct 36 ms 35756 KB Output is correct
5 Correct 37 ms 35764 KB Output is correct
6 Correct 36 ms 35684 KB Output is correct
7 Correct 37 ms 36244 KB Output is correct
8 Correct 36 ms 36068 KB Output is correct
9 Correct 36 ms 35792 KB Output is correct
10 Correct 36 ms 35956 KB Output is correct
11 Correct 36 ms 35636 KB Output is correct
12 Correct 48 ms 45172 KB Output is correct
13 Correct 40 ms 36476 KB Output is correct
14 Correct 38 ms 36080 KB Output is correct
15 Correct 39 ms 35808 KB Output is correct
16 Correct 36 ms 35752 KB Output is correct
17 Correct 37 ms 36180 KB Output is correct
18 Correct 36 ms 35956 KB Output is correct
19 Correct 43 ms 35900 KB Output is correct
20 Correct 43 ms 35964 KB Output is correct
21 Correct 42 ms 35836 KB Output is correct
22 Correct 43 ms 35976 KB Output is correct
23 Correct 47 ms 35756 KB Output is correct
24 Correct 48 ms 35760 KB Output is correct
25 Correct 43 ms 35720 KB Output is correct
26 Correct 36 ms 35712 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 84192 KB Output is correct
2 Correct 193 ms 84148 KB Output is correct
3 Correct 214 ms 84076 KB Output is correct
4 Correct 223 ms 84680 KB Output is correct
5 Correct 155 ms 82764 KB Output is correct
6 Correct 146 ms 82764 KB Output is correct
7 Correct 153 ms 82724 KB Output is correct
8 Correct 143 ms 82652 KB Output is correct
9 Correct 171 ms 98256 KB Output is correct
10 Correct 152 ms 90772 KB Output is correct
11 Correct 161 ms 83708 KB Output is correct
12 Correct 143 ms 82856 KB Output is correct
13 Correct 151 ms 82968 KB Output is correct
14 Correct 173 ms 83500 KB Output is correct
15 Correct 216 ms 83980 KB Output is correct
16 Correct 213 ms 83996 KB Output is correct
17 Correct 148 ms 82776 KB Output is correct
18 Correct 148 ms 82936 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 85096 KB Output is correct
2 Correct 227 ms 85272 KB Output is correct
3 Correct 462 ms 151432 KB Output is correct
4 Correct 203 ms 84788 KB Output is correct
5 Correct 285 ms 146760 KB Output is correct
6 Correct 251 ms 146712 KB Output is correct
7 Correct 159 ms 83596 KB Output is correct
8 Correct 193 ms 112276 KB Output is correct
9 Correct 168 ms 98224 KB Output is correct
10 Correct 258 ms 146212 KB Output is correct
11 Correct 254 ms 146364 KB Output is correct
12 Correct 248 ms 146620 KB Output is correct
13 Correct 340 ms 147172 KB Output is correct
14 Correct 542 ms 149496 KB Output is correct
15 Correct 325 ms 148152 KB Output is correct
16 Correct 298 ms 148160 KB Output is correct
17 Correct 254 ms 146912 KB Output is correct
18 Correct 237 ms 147008 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1052 ms 295864 KB Output is correct
2 Correct 1072 ms 295748 KB Output is correct
3 Correct 1501 ms 353556 KB Output is correct
4 Correct 1016 ms 295968 KB Output is correct
5 Correct 664 ms 361384 KB Output is correct
6 Correct 650 ms 350024 KB Output is correct
7 Correct 518 ms 287008 KB Output is correct
8 Correct 619 ms 334968 KB Output is correct
9 Correct 598 ms 349320 KB Output is correct
10 Correct 641 ms 360600 KB Output is correct
11 Correct 637 ms 361136 KB Output is correct
12 Correct 687 ms 361728 KB Output is correct
13 Correct 1000 ms 362920 KB Output is correct
14 Correct 1630 ms 358312 KB Output is correct
15 Correct 962 ms 350180 KB Output is correct
16 Correct 904 ms 352248 KB Output is correct
17 Correct 608 ms 342988 KB Output is correct
18 Correct 612 ms 342288 KB Output is correct