Submission #261674

#	Time	Username	Problem	Language	Result	Execution time	Memory
261674		oscarsierra12	Jousting tournament (IOI12_tournament)	C++14	0 / 100	1093 ms	4852 KiB

tournament

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>

using namespace std ;

const int No = 2e5;

long long mx[10*No] ;
vector <long long> l, r ;
vector <pair<long long, long long>> in;
vector <long long> vals;

void update (int node, int lw, int rg, int a, long long v) {
    if ( lw == a && rg == a ) {
        mx[node] = v ;
        return  ;
    }
    int m = (lw + rg) >> 1 ;
    if ( a <= m ) update ( node << 1, lw, m, a, v) ;
    else update ( (node<<1) + 1, m+1, rg, a, v ) ;
    mx[node] = max ( mx[node<<1], mx[(node<<1)+1] ) ;
}

long long query ( int node, int lw, int rg, int a, int b ) {
    if ( b < lw || rg < a ) return 0 ;
    if ( a <= lw && rg <= b ) return mx[node] ;
    int m = (lw + rg) >> 1 ;
    return max ( query(node<<1, lw, m, a, b), query ((node<<1)+1, m+1, rg, a, b) );
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  for ( int i = 0 ; i < N-1 ; ++i ) vals.push_back(K[i]) ;
  for ( int i = 0 ; i < N-1 ; ++i ) in.push_back ({0, -i}), l.push_back (i), r.push_back (i), update (1, 0, No-1, i, K[i]) ;
  pair <long long, long long> ans = {INT_MIN, -1};
  for ( int i = 0 ; i < C ; ++i ) {
    pair <long long, long long> incur = {INT_MIN, -1};
    long long lcur = INT_MAX, rcur = INT_MIN, mxcur = INT_MIN;
    for ( int j = S[i] ; j <= E[i] ; ++j ) {
        if ( S[i] >= vals.size() ) break ;
        incur = max ( incur, in[S[i]] ) ;
        lcur = min ( lcur, l[S[i]] ) ;
        rcur = max ( rcur, r[S[i]] ) ;
        mxcur = max ( mxcur, vals[S[i]] ) ;
        vals.erase ( vals.begin() + S[i] ) ;
        l.erase ( l.begin() + S[i] ) ;
        r.erase ( r.begin() + S[i] ) ;
        in.erase ( in.begin() + S[i] ) ;
    }
    vals.insert (vals.begin() + S[i], mxcur ) ;
    l.insert ( l.begin() + S[i], lcur ) ;
    r.insert ( r.begin() + S[i], rcur ) ;
    in.insert ( in.begin() + S[i], incur ) ;
    if ( S[i] < in.size() ) in[S[i]].first++ ;
    if ( S[i] < in.size()  && query (1, 0,No-1, l[S[i]], r[S[i]]-1) < R ) ans = max ( ans, in[S[i]] ) ;
  }
  return -ans.second ;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if ( S[i] >= vals.size() ) break ;
              ~~~~~^~~~~~~~~~~~~~
tournament.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( S[i] < in.size() ) in[S[i]].first++ ;
          ~~~~~^~~~~~~~~~~
tournament.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( S[i] < in.size()  && query (1, 0,No-1, l[S[i]], r[S[i]]-1) < R ) ans = max ( ans, in[S[i]] ) ;
          ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51