Submission #925439

#	Time	Username	Problem	Language	Result	Execution time	Memory
925439		anton	Jousting tournament (IOI12_tournament)	C++17	100 / 100	176 ms	9928 KiB

tournament

#include<bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
 
typedef tree<
  pair<int,int>,
  null_type,
  less<pair<int,int>>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;


struct AddTree{
  vector<int> tr;
  int bar= 1;
  void init(int _sz){
    while(bar<_sz){
      bar*=2;
    }
    tr.resize(2*bar, 0);
  }

  void add(int l, int r, int v){
    l+=bar;
    r+=bar+1;

    int res= 0;
    for(; l<r; l/=2, r/=2){
      if(l%2==1){
        tr[l++]+=v;
      }
      if(r%2==1){
        tr[--r]+=v;
      }
    }
  }

  int get(int id){
    id+=bar;
    int res= 0;
    for(int i = id; i>=1; i/=2){
        res+=tr[i];
    }
    return res;
  }
};
struct Tree{
  vector<int> tr;
  int bar= 1;
  void init(int _sz){
    while(bar<_sz){
      bar*=2;
    }
    tr.resize(2*bar, 0);
  }

  int get(int l, int r){
    l+=bar;
    r+=bar+1;


    int res= 0;
    for(; l<r; l/=2, r/=2){
      if(l%2==1){
        res= max(res, tr[l++]);
      }
      if(r%2==1){
        res= max(res, tr[--r]);
      }
    }
    return res;
  }

  void upd(){
    for(int i = bar-1; i>=1; i--){
      tr[i] = max(tr[i*2], tr[i*2+1]);
    }
  }
};



int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

    ordered_set os;
    vector<pii> affected;

    for(int i = 0; i<N; i++){
        os.insert(pii(i, i));
    }

    for(int i = 0; i<C; i++){
        int l = S[i];
        int r= E[i];
        auto it = os.find_by_order(l);
        auto itend = os.find_by_order(r);
        pii interval = {it->first, itend->second};
        affected.push_back(interval);
        for(int i = l; i<=r; i++){
            os.erase(os.find_by_order(l));
        }
        
        os.insert(interval);
    }

    Tree cur;
    cur.init(N);
    for(int i = 0; i<N-1; i++){
        cur.tr[i+cur.bar] = K[i];
    }

    cur.upd();

    AddTree tr;
    tr.init(N);

    for(int i = 0; i<C; i++){

        //case 2: knight in the interval
        int winer = cur.get(affected[i].first, affected[i].second-1);
        //cout<<"winner "<<winer<<endl;
        if(winer<=R){
            tr.add(affected[i].first, affected[i].second, 1);
        }


    }

    pii best = {-1, 0};
    for(int i = 0; i<N; i++){
        if(tr.get(i)>best.first){
            best.first = tr.get(i);
            best.second = i;
        }
    }

    return best.second;

}

Compilation message (stderr)

tournament.cpp: In member function 'void AddTree::add(int, int, int)':
tournament.cpp:32:9: warning: unused variable 'res' [-Wunused-variable]
   32 |     int res= 0;
      |         ^~~

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