結果

問題 No.814 ジジ抜き
ユーザー beetbeet
提出日時 2019-04-12 22:57:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,999 bytes
コンパイル時間 2,376 ms
コンパイル使用メモリ 219,920 KB
実行使用メモリ 661,888 KB
最終ジャッジ日時 2024-09-15 06:07:15
合計ジャッジ時間 7,916 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,624 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 MLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

Int cnt_inc=0;
struct DS{
  using P = pair<Int, Int>;
  set<P> sp;
  // [l, r)
  
  void add(Int l,Int r){    
    cnt_inc++;
    if(cnt_inc>1e7) exit(1);    
    assert(l!=r);
    if(sp.empty()){
      sp.emplace(l,r);
      return;
    }
    while(1){
      auto it=sp.upper_bound(P(l,l));
      if(it==sp.begin()) break;        
      it--;        
      Int pl,pr;
      tie(pl,pr)=*it;
      assert(pl<l);
        
      if(pr<=l) break;
      if(r<=pr){
        sp.erase(P(pl,pr));
        if(pl!=l) sp.emplace(pl,l);
        if(r!=pr) sp.emplace(r,pr);
        return;
      }
        
      if(pl!=l) sp.emplace(pl,l);
      l=pr;
      break;
    }
    while(l<r){
      auto it=sp.upper_bound(P(l,l));
      if(it==sp.end()){
        if(l!=r) sp.emplace(l,r);
        break;
      }
      Int nl,nr;
      tie(nl,nr)=*it;
      assert(l<=nl);
      if(r<=nl){
        if(l!=r) sp.emplace(l,r);
        break;
      }
      if(r<=nr){
        sp.erase(P(nl,nr));
        if(l!=nl) sp.emplace(l,nl);
        if(r!=nr) sp.emplace(r,nr);
        return;
      }
        
      assert(nr<r);
      sp.erase(P(nl,nr));
      if(l!=nl) sp.emplace(l,nl);
      l=nr;
    }
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n),b(n),c(n);
  for(Int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i];


  vector<Int> l(n),r(n),v(n),w(n);
  for(Int i=0;i<n;i++){
    w[i]=1LL<<c[i];
    v[i]=b[i]%w[i];
    l[i]=b[i]/w[i];
    r[i]=l[i]+a[i];
    // cout<<v[i]<<" "<<w[i]<<" "<<l[i]<<" "<<r[i]<<endl;
  }


  map<Int, DS> dp;
  for(Int t=0;t<60;t++){
    for(Int i=0;i<n;i++){
      if(c[i]!=t) continue;
      dp[v[i]].add(l[i],r[i]);
    }    
    map<Int, DS> nx;
    for(auto &st:dp){
      Int x=st.first;
      for(auto p:st.second.sp){
        // cout<<t<<" "<<x<<":"<<p.first<<" "<<p.second<<endl;
        Int n0=x;
        Int n1=x|(1LL<<t);

        Int l0=(p.first+1)>>1;
        Int l1=l0-(p.first&1);
        
        Int r0=(p.second+1)>>1;
        Int r1=r0-(p.second&1);

        assert(p.first<=l0*2&&p.second<=r0*2);
        assert(p.first<=l1*2+1&&p.second<=r1*2+1);
        
        assert(p.first>l0*2-2&&p.second>r0*2-2);
        assert(p.first>l1*2-1&&p.second>r1*2-1);

        //cout<<":"<<l0<<" "<<r0<<":"<<l1<<" "<<r1<<endl;
        if(l0!=r0) nx[n0].add(l0,r0);
        if(l1!=r1) nx[n1].add(l1,r1);        
      }
      st.second.sp.clear();
    }
    dp.clear();
    swap(dp,nx);    
  }

  Int cnt=0;
  for(auto &p:dp){
    if(p.second.sp.empty()) continue;
    auto it=p.second.sp.begin();
    assert((it->first)+1==(it->second));
    Int x=p.first+(1LL<<60)*(it->first);
    cout<<x<<endl;
    cnt++;
  }
  assert(cnt==1);
  return 0;
}
0