제출 #1237846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237846		guanex	Jousting tournament (IOI12_tournament)	C++20	100 / 100	48 ms	5504 KiB

tournament

#include<bits/stdc++.h>

using namespace std;


struct lazysegtree{
  vector<int> t;
  vector<bool> lazy;
  lazysegtree(int n){
    t.assign(4 * (n+1), 0);
    lazy.assign(4*(n+1), false);
    build(1, 0, n);
  }
  void build(int no, int lo, int hi){
    if(lo == hi){
      t[no] = 1;
      return;
    }
    int mid = lo + (hi - lo) / 2;
    build(2*no, lo, mid);
    build(2*no+1, mid+1, hi);
    t[no] = t[2*no] + t[2*no+1];
  }
  void propagate(int no){
    if(lazy[no] == 0)return;
    t[2*no] = 0;
    t[2*no+1] = 0;
    lazy[2*no] = 1;
    lazy[2*no+1] = 1;
    lazy[no] = 0;
  }
  void update(int no, int lo, int hi, int l, int r){
    if(lo == l && hi == r){
      t[no] = 0;
      lazy[no] = 1;
      return;
    }
    int mid = lo + (hi - lo) / 2;
    //cout << no << " " << l << " " << r << " " << lo << " " << hi << endl;
    propagate(no);
    if(r <= mid){
      update(2*no, lo, mid, l, r);
    }else if(l > mid){
      update(2*no+1, mid+1, hi, l, r);
    }else{
      update(2*no, lo, mid, l, mid);
      update(2*no+1, mid+1, hi, mid+1, r);
    }
    t[no] = t[2*no] + t[2*no+1];
  }

  int query(int no, int lo, int hi, int tar, int sum){
    if(lo == hi){
      return lo;
    }
    int mid = lo + (hi - lo) / 2;
    //cout << no << " " << t[no] << " " << sum << tar << endl;
    assert(t[no] + sum >= tar);
    if(t[2*no]+sum >= tar){
      return query(2*no, lo, mid, tar, sum);
    }else{
      sum += t[2*no];
      return query(2*no+1, mid+1, hi, tar, sum);
    }
  } 

};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  vector<int> pref(N+1);
  vector<int> suff(N+1);
  vector<int> knights;
  int defeat = 0;
  for(int i = 0; i < N-1; ++i){
    if(K[i] > R){
      defeat++;
      pref[i]++;
      suff[i]++;
    }
  }
  vector<pair<int, int>> x;
  for(int i = 0; i < N; ++i){
    pref[i+1] += pref[i];
    suff[N-i-1] += suff[N-i];
    x.push_back({i, i});
  }
  x.push_back({N, N});
  vector<int> sweep(N+1);
  lazysegtree tree(N);
  for(int i = 0; i < C; ++i){
    //cout << i << endl;
    int l = tree.query(1, 0, N, S[i]+1, 0);
    int r = tree.query(1, 0, N, E[i]+2, 0)-1;
    //cout << l << " " << r << endl;
    tree.update(1, 0, N, l+1, r);
    if(l > 0){
      if(pref[l-1] + suff[r] >= defeat){
        sweep[l]++;
        sweep[r+1]--;
      }
    }else{
      if(suff[r] >= defeat){
        sweep[l]++;
        sweep[r+1]--; 
      }
    }
  }
  int ans = -1;
  int act = 0;
  int pos = 0;
  for(int i = 0; i <= N-1; ++i){
    act += sweep[i];
    if(act > ans){
      ans = act;
      pos = i;
    }
  }
  return pos;
}

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