oj.uz

Submission #925439

# Submission time Handle Problem Language Result Execution time Memory
925439 2024-02-11T15:56:45 Z anton Jousting tournament (IOI12_tournament) C++17
100 / 100
 176 ms 9928 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 872 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 604 KB Output is correct
6 Correct 4 ms 704 KB Output is correct
7 Correct 4 ms 860 KB Output is correct
8 Correct 5 ms 860 KB Output is correct
9 Correct 3 ms 736 KB Output is correct
10 Correct 5 ms 856 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4812 KB Output is correct
2 Correct 173 ms 9552 KB Output is correct
3 Correct 115 ms 7652 KB Output is correct
4 Correct 152 ms 9928 KB Output is correct
5 Correct 153 ms 9256 KB Output is correct
6 Correct 162 ms 9264 KB Output is correct
7 Correct 175 ms 9608 KB Output is correct
8 Correct 176 ms 9704 KB Output is correct
9 Correct 93 ms 7440 KB Output is correct
10 Correct 111 ms 7676 KB Output is correct