Submission #483687

#	Time	Username	Problem	Language	Result	Execution time	Memory
483687		yusufake	Teams (IOI15_teams)	C++98	100 / 100	1267 ms	159068 KiB

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;

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 n;
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 las, req, x;
        las = req = x = K[i];
        int ex = 0;
        for(;;){
            int y = S.top().st;
            int z = S.top().nd.st;
            if(z < las){
                S.pop();
                continue;
            }
            if(z == las){
                ex += S.top().nd.nd;
                S.pop();
                continue;
            }

            int l = binary_search(root[x], root[y], 1, n, req + ex + query(root[x], root[y], 1, n, 1, las-1) );
            int t = S.top().nd.st;
            if(l >= t){
                req -= query(root[x], root[y], 1, n, las, t-1) - ex;
                las = t;
                ex = S.top().nd.nd;
                S.pop();
                continue;
            }
            else{
                req -= query(root[x], root[y], 1, n, las, 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 (stderr)

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

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