oj.uz

Submission #261681

# Submission time Handle Problem Language Result Execution time Memory
261681 2020-08-12T00:33:50 Z oscarsierra12 Jousting tournament (IOI12_tournament) C++14
17 / 100
 1000 ms 1656 KB 
#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]) ;
  pair <long long, long long> ans = {-1e17, -1};
  for ( int i = 0 ; i < N ; ++i ) {
      vector <long long> bf = vals ;
      vals.insert (vals.begin() + i, R ) ;
      int cur = 0 ;
      for ( int i = 0 ; i < C ; ++i ) {
        pair <long long, long long> incur = {-1e17, -1};
        long long mxcur = -1e17 ;
        for ( int j = S[i] ; j <= E[i] ; ++j ) {
            mxcur = max ( mxcur, vals[S[i]] ) ;
            vals.erase ( vals.begin() + S[i] ) ;
        }
        vals.insert (vals.begin() + S[i], mxcur ) ;
        if ( vals[S[i]] == R ) cur++ ;
      }
      ans = max ( ans, {cur, -i}) ;
        vals = bf ;
  }
  return -ans.second ;
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:56:37: warning: variable 'incur' set but not used [-Wunused-but-set-variable]
         pair <long long, long long> incur = {-1e17, -1};
                                     ^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 140 ms 376 KB Output is correct
4 Correct 45 ms 256 KB Output is correct
5 Correct 198 ms 376 KB Output is correct
6 Correct 112 ms 376 KB Output is correct
7 Correct 80 ms 256 KB Output is correct
8 Correct 85 ms 376 KB Output is correct
9 Correct 62 ms 376 KB Output is correct
10 Correct 62 ms 384 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 1656 KB Time limit exceeded
2 Halted 0 ms 0 KB -