Submission #69885

#	Time	Username	Problem	Language	Result	Execution time	Memory
69885		yusufake	Teams (IOI15_teams)	C++98	100 / 100	1675 ms	205196 KiB

teams

#include<bits/stdc++.h>
using namespace std;
#include "teams.h"

#define mx 500005
#define tm (tl+tr >> 1)
int s[mx*20],L[mx*20],R[mx*20],root[mx],nw;
int up(int v, int tl, int tr, int i){
    if(tl > i || tr < i) return v;
    int w = ++nw;
    if(tl < tr){
        L[w] = up(L[v],tl,tm,i);
        R[w] = up(R[v],tm+1,tr,i);
    }
    s[w] = s[v]+1;
    return w;
}
int qry(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 qry(L[a],L[b],tl,tm,l,r) + qry(R[a],R[b],tm+1,tr,l,r);
}

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

#define mp make_pair
#define st first
#define nd second
int n;
int can(int m, int *K){
    int t,i,l,md,r,x,y,z,las,req,ex;
    stack < pair < int , pair<int,int> > > S;
    S.push(mp(0,mp(mx,0)));
    sort(K , K+m);
    for(i=0;i<m;i++){
        las = req = x = K[i];
        ex = 0;
        for(;;){
            y = S.top().st;
            z = S.top().nd.st;
            if(z < las){
                S.pop();
                continue;
            }
            if(z == las){
                ex += S.top().nd.nd;
                S.pop();
                continue;
            }
/*          l = las;
            r = n+1;
            for(; l<r ;){
                md = l+r >> 1;
                if(qry(root[x],root[y],1,n,las,md)-ex >= req) r = md;
                else l = md+1;
            }
            */
            l = bs(root[x],root[y],1,n, req+ex+qry(root[x],root[y],1,n,1,las-1) );
            if(l >= (t = S.top().nd.st)){
                req -= qry(root[x],root[y],1,n,las,t-1) - ex;
                las = t;
                ex = S.top().nd.nd;
                S.pop();
                continue;
            }
            else{
                //cout << x << " " << y << " " << req <<" " << ex << " zz\n"; 
                req -= qry(root[x],root[y],1,n,las,l)-ex;
                //cout << i << " " << las << " " << l << " " << req << " ss\n";
                if(req > 0) return 0;
                ex = req + qry(root[x],root[y],1,n,l,l);
                S.push(mp(x,mp(l,ex)));
                break;
            }
        }
    }
    return 1;
}

vector < int > V[mx];
void init(int ss, int *a, int *b){
    n = ss;
    int i,j,p=0;
    for(i=0;i<n;i++) V[ a[i] ].push_back(b[i]);
    for(i=1;i<=n;i++){
        for(j=0;j<V[i].size();j++)
            p = up(p,1,n,V[i][j]);
        root[i] = p;
    }
}

Compilation message (stderr)

teams.cpp: In function 'int up(int, int, int, int)':
teams.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
teams.cpp:12:27: note: in expansion of macro 'tm'
         L[w] = up(L[v],tl,tm,i);
                           ^~
teams.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
teams.cpp:13:24: note: in expansion of macro 'tm'
         R[w] = up(R[v],tm+1,tr,i);
                        ^~
teams.cpp: In function 'int qry(int, int, int, int, int, int)':
teams.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
teams.cpp:21:29: note: in expansion of macro 'tm'
     return qry(L[a],L[b],tl,tm,l,r) + qry(R[a],R[b],tm+1,tr,l,r);
                             ^~
teams.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
teams.cpp:21:53: note: in expansion of macro 'tm'
     return qry(L[a],L[b],tl,tm,l,r) + qry(R[a],R[b],tm+1,tr,l,r);
                                                     ^~
teams.cpp: In function 'int bs(int, int, int, int, int)':
teams.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
teams.cpp:27:29: note: in expansion of macro 'tm'
         return bs(R[a],R[b],tm+1,tr,k-(s[ L[a] ] - s[ L[b] ]));
                             ^~
teams.cpp:6:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl+tr >> 1)
             ~~^~
teams.cpp:28:28: note: in expansion of macro 'tm'
     return bs(L[a],L[b],tl,tm,k);
                            ^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:36:15: warning: unused variable 'md' [-Wunused-variable]
     int t,i,l,md,r,x,y,z,las,req,ex;
               ^~
teams.cpp:36:18: warning: unused variable 'r' [-Wunused-variable]
     int t,i,l,md,r,x,y,z,las,req,ex;
                  ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<V[i].size();j++)
                 ~^~~~~~~~~~~~

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