oj.uz

Submission #489852

# Submission time Handle Problem Language Result Execution time Memory
489852 2021-11-25T00:49:35 Z yusufake Teams (IOI15_teams) C++
100 / 100
 1245 ms 158980 KB 
// persistent segment tree example
// https://oj.uz/problem/view/IOI15_teams
#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
#define mp make_pair
#define st first
#define nd second
#define N 500005
#define tm (tl+tr >> 1)

int s[N * 20], L[N * 20], R[N * 20], root[N], nw, n;

int update(int v, int tl, int tr, int i){
    if(tl > i || tr < i) return v;
    int w = ++nw;
    if(tl < tr){
        L[w] = update(L[v], tl, tm, i);
        R[w] = update(R[v], tm+1, tr, i);
    }
    s[w] = s[v] + 1;
    return w;
}

int query(int a, int b, int tl, int tr, int l, int r){
    if(tl > r || tr < l) return 0;
    if(tl >= l && tr <= r) return s[a] - s[b];
    return query(L[a], L[b], tl, tm, l, r) + query(R[a], R[b], tm+1, tr, l, r);
}

int binary_search(int a, int b, int tl, int tr, int k){
    if(tl == tr) return tl;
    if(s[ L[a] ] - s[ L[b] ] < k)
        return binary_search(R[a], R[b], tm+1, tr, k - (s[ L[a] ] - s[ L[b] ]));
    return binary_search(L[a], L[b], tl, tm, k);
}

int can(int m, int *K){
    stack < pair < int , pair< int, int > > > S;
    S.push(mp(0, mp(N, 0)));
    sort(K, K + m);
    for(int i = 0; i < m; i++){
        int last, req, x;
        last = req = x = K[i];
        int ex = 0;
        for(;;){
            int z = S.top().nd.st;
            if(z < last){
                S.pop();
                continue;
            }
            if(z == last){
                ex += S.top().nd.nd;
                S.pop();
                continue;
            }

            int y = S.top().st;
            int t = S.top().nd.st;
            int l = binary_search(root[x], root[y], 1, n, req + ex + query(root[x], root[y], 1, n, 1, last - 1));
            if(l >= t){
                req -= query(root[x], root[y], 1, n, last, t-1) - ex;
                last = t;
                ex = S.top().nd.nd;
                S.pop();
                continue;
            }
            else{
                req -= query(root[x], root[y], 1, n, last, l) - ex;
                if(req > 0)
                    return 0;
                ex = req + query(root[x], root[y], 1, n, l, l);
                S.push(mp(x, mp(l, ex)));
                break;
            }
        }
    }

    return 1;
}

vector < int > V[N];
void init(int ss, int *a, int *b){
    n = ss;
    for(int i = 0; i < n; i++)
        V[ a[i] ].push_back(b[i]);
    
    int p = 0;
    for(int i = 1; i <= n; i++){
        for(auto t: V[i])
            p = update(p, 1, n, t);
        root[i] = p;
    }
}

Compilation message

teams.cpp: In function 'int update(int, int, int, int)':
teams.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 | #define tm (tl+tr >> 1)
      |             ~~^~~
teams.cpp:18:33: note: in expansion of macro 'tm'
   18 |         L[w] = update(L[v], tl, tm, i);
      |                                 ^~
teams.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 | #define tm (tl+tr >> 1)
      |             ~~^~~
teams.cpp:19:29: note: in expansion of macro 'tm'
   19 |         R[w] = update(R[v], tm+1, tr, i);
      |                             ^~
teams.cpp: In function 'int query(int, int, int, int, int, int)':
teams.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 | #define tm (tl+tr >> 1)
      |             ~~^~~
teams.cpp:28:34: note: in expansion of macro 'tm'
   28 |     return query(L[a], L[b], tl, tm, l, r) + query(R[a], R[b], tm+1, tr, l, r);
      |                                  ^~
teams.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 | #define tm (tl+tr >> 1)
      |             ~~^~~
teams.cpp:28:64: note: in expansion of macro 'tm'
   28 |     return query(L[a], L[b], tl, tm, l, r) + query(R[a], R[b], tm+1, tr, l, r);
      |                                                                ^~
teams.cpp: In function 'int binary_search(int, int, int, int, int)':
teams.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 | #define tm (tl+tr >> 1)
      |             ~~^~~
teams.cpp:34:42: note: in expansion of macro 'tm'
   34 |         return binary_search(R[a], R[b], tm+1, tr, k - (s[ L[a] ] - s[ L[b] ]));
      |                                          ^~
teams.cpp:10:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   10 | #define tm (tl+tr >> 1)
      |             ~~^~~
teams.cpp:35:42: note: in expansion of macro 'tm'
   35 |     return binary_search(L[a], L[b], tl, tm, k);
      |                                          ^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 7 ms 12048 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 6 ms 12044 KB Output is correct
5 Correct 7 ms 12048 KB Output is correct
6 Correct 7 ms 12060 KB Output is correct
7 Correct 6 ms 11980 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 7 ms 12052 KB Output is correct
10 Correct 6 ms 11980 KB Output is correct
11 Correct 6 ms 12080 KB Output is correct
12 Correct 8 ms 12108 KB Output is correct
13 Correct 8 ms 12016 KB Output is correct
14 Correct 6 ms 11980 KB Output is correct
15 Correct 7 ms 12108 KB Output is correct
16 Correct 7 ms 11980 KB Output is correct
17 Correct 7 ms 12020 KB Output is correct
18 Correct 7 ms 11980 KB Output is correct
19 Correct 6 ms 12056 KB Output is correct
20 Correct 6 ms 12020 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 6 ms 12108 KB Output is correct
23 Correct 6 ms 11980 KB Output is correct
24 Correct 6 ms 11980 KB Output is correct
25 Correct 7 ms 11980 KB Output is correct
26 Correct 8 ms 11980 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 36832 KB Output is correct
2 Correct 67 ms 36832 KB Output is correct
3 Correct 64 ms 36940 KB Output is correct
4 Correct 88 ms 37528 KB Output is correct
5 Correct 38 ms 35420 KB Output is correct
6 Correct 35 ms 35408 KB Output is correct
7 Correct 34 ms 35440 KB Output is correct
8 Correct 35 ms 35372 KB Output is correct
9 Correct 54 ms 34504 KB Output is correct
10 Correct 42 ms 34108 KB Output is correct
11 Correct 35 ms 35364 KB Output is correct
12 Correct 33 ms 34332 KB Output is correct
13 Correct 42 ms 35984 KB Output is correct
14 Correct 65 ms 35448 KB Output is correct
15 Correct 59 ms 36656 KB Output is correct
16 Correct 59 ms 36680 KB Output is correct
17 Correct 47 ms 35904 KB Output is correct
18 Correct 38 ms 36080 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 37712 KB Output is correct
2 Correct 85 ms 37796 KB Output is correct
3 Correct 258 ms 41180 KB Output is correct
4 Correct 70 ms 37464 KB Output is correct
5 Correct 83 ms 36128 KB Output is correct
6 Correct 97 ms 36212 KB Output is correct
7 Correct 40 ms 36228 KB Output is correct
8 Correct 69 ms 36144 KB Output is correct
9 Correct 69 ms 34460 KB Output is correct
10 Correct 102 ms 34668 KB Output is correct
11 Correct 107 ms 36032 KB Output is correct
12 Correct 132 ms 35080 KB Output is correct
13 Correct 209 ms 36932 KB Output is correct
14 Correct 309 ms 39188 KB Output is correct
15 Correct 128 ms 37712 KB Output is correct
16 Correct 137 ms 37584 KB Output is correct
17 Correct 77 ms 36728 KB Output is correct
18 Correct 87 ms 36704 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 152100 KB Output is correct
2 Correct 493 ms 152120 KB Output is correct
3 Correct 1113 ms 158980 KB Output is correct
4 Correct 494 ms 151856 KB Output is correct
5 Correct 308 ms 143476 KB Output is correct
6 Correct 321 ms 143500 KB Output is correct
7 Correct 197 ms 143544 KB Output is correct
8 Correct 247 ms 143528 KB Output is correct
9 Correct 268 ms 136736 KB Output is correct
10 Correct 288 ms 141044 KB Output is correct
11 Correct 305 ms 141688 KB Output is correct
12 Correct 353 ms 142644 KB Output is correct
13 Correct 691 ms 146004 KB Output is correct
14 Correct 1245 ms 153696 KB Output is correct
15 Correct 481 ms 150648 KB Output is correct
16 Correct 558 ms 150544 KB Output is correct
17 Correct 283 ms 145124 KB Output is correct
18 Correct 283 ms 145020 KB Output is correct