Submission #306469


Source Code Expand

#ifdef KOMAKI_LOCAL
#include <omp.h>
#else
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
#define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; }
#define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; }
#define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; }
#define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; }
#define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; }
#define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; }
#define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; }
















/**********************************************/
/* 1. Initialization. Search 'initialization' */
/* 2. Update. Search 'update('                */
/* 3. Get. Search 'get(int v, '               */
/**********************************************/

template <typename T>
class SegmentTreeTemplate
{
public:

  void update(int pos, T value)
  {
    pos += size;
    tree[pos] = value;
    
    while(1 < pos){
      pos >>= 1;
      tree[pos] = tree[pos * 2 + 0] * tree[pos * 2 + 1];
    }
  }

  T get(int l, int r){ return get(1, 0, size, l, r); }
  T get(int v, int current_l, int current_r, int l, int r)
  {
    if(current_r <= l || r <= current_l){
      return 1;
    }
    
    if(l <= current_l && current_r <= r){
      return tree[v];
    }
    
    int mid = (current_l + current_r) >> 1;

    return get(v * 2 + 0, current_l, mid, l, r) * get(v * 2 + 1, mid, current_r, l, r);
  }
  
  SegmentTreeTemplate(int size_arg)
  {
    for(size = 1; size < size_arg; size <<= 1);
    tree = new T[size * 2];

    for(int i = 0; i < size * 2; ++i) tree[i] = 1;
  }
  
  
  SegmentTreeTemplate();
  ~SegmentTreeTemplate();
private:

  int size;
  T* tree;
};


template <typename T>
inline SegmentTreeTemplate<T>::SegmentTreeTemplate()
{
  this->size = 1;
  tree = new T[this->size * 2];
}

template <typename T>
inline SegmentTreeTemplate<T>::~SegmentTreeTemplate()
{
  delete [] tree;
}



int main()
{
  i64 n;
  cin >> n;
  vector<tuple<i64, i64, i64>> v(n);
  rep(i, n) cin >> get<0>(v[i]) >> get<1>(v[i]);

  vector<tuple<i64, i64, i64>> q;
  rep(i, n){
    q.push_back(make_tuple(get<0>(v[i]), i, 0));
    q.push_back(make_tuple(get<1>(v[i]), i, 1));
  }
  sort(all(q));

  SegmentTreeTemplate<double> tree(sz(q) + 10);

  double remain = 0;
  rep(i, sz(q)){
    if(get<2>(q[i]) == 0){
      remain += 1.0;
      get<0>(v[get<1>(q[i])]) = i;
    }else{
      tree.update(i, (remain - 1.0) / remain);
      remain -= 1.0;
      get<1>(v[get<1>(q[i])]) = i;
    }
  }

  rep(i, n){
    double bef = tree.get(get<0>(v[i]), get<1>(v[i]));
    double cur = tree.get(get<0>(v[i]), get<1>(v[i]) + 1);
    printf("%0.10lf %0.10lf\n", 1.0 - bef, cur);
  }
}














Submission Info

Submission Time
Task F - Yakiniku
User Komaki
Language C++11 (GCC 4.8.1)
Score 100
Code Size 6211 Byte
Status AC
Exec Time 436 ms
Memory 12060 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 22
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_random09.txt, subtask1_random10.txt, subtask1_random11.txt, subtask1_random12.txt, subtask1_random13.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 26 ms 792 KB
subtask0_sample_02.txt AC 22 ms 800 KB
subtask0_sample_03.txt AC 22 ms 676 KB
subtask1_random01.txt AC 23 ms 740 KB
subtask1_random02.txt AC 23 ms 804 KB
subtask1_random03.txt AC 22 ms 920 KB
subtask1_random04.txt AC 24 ms 924 KB
subtask1_random05.txt AC 24 ms 808 KB
subtask1_random06.txt AC 23 ms 804 KB
subtask1_random07.txt AC 22 ms 796 KB
subtask1_random08.txt AC 22 ms 932 KB
subtask1_random09.txt AC 428 ms 12052 KB
subtask1_random10.txt AC 433 ms 12000 KB
subtask1_random11.txt AC 432 ms 12044 KB
subtask1_random12.txt AC 432 ms 12060 KB
subtask1_random13.txt AC 436 ms 12044 KB
subtask1_special01.txt AC 343 ms 12040 KB
subtask1_special02.txt AC 313 ms 11980 KB
subtask1_special03.txt AC 353 ms 11996 KB
subtask1_special04.txt AC 21 ms 924 KB
subtask1_special05.txt AC 22 ms 804 KB
subtask1_special06.txt AC 21 ms 924 KB