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 |
|
|
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 |