Submission #527822
Source Code Expand
/*{{{*/
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
typedef int8_t sbyte;
typedef uint8_t byte;
typedef uint16_t ushort;
typedef uint32_t uint;
typedef int64_t i64;
typedef uint64_t u64;
template<class T> static inline T ABS(T x) {return x < 0 ? -x : x;}
template<class T> static inline void MAZ(T &a, const T &b) {if(a < b) a = b;}
template<class T> static inline void MIZ(T &a, const T &b) {if(b < a) a = b;}
/*}}}*/
static int ql, qr;
static double qx, seg[262144];
static int leaf[131072];
#define __ auto m = l + r >> 1
#define _0 (u << 1)
#define _1 (_0 | 1)
static void go(int u, int l, int r) {
if(ql <= l && r <= qr) {
qx *= seg[u];
} else {
__;
if(ql <= m) go(_0, l, m);
if(qr > m) go(_1, m + 1, r);
}
}
static void build(int u, int l, int r) {
seg[u] = 1;
__;
if(l == r) {
leaf[m] = u;
} else {
build(_0, l, m);
build(_1, m + 1, r);
}
}
int main() {
int n;
scanf("%d", &n);
vector<pair<int, int>> v;
for(auto i = 1; i <= n; i++) {
int a, b;
scanf("%d%d", &a, &b);
v.emplace_back(a, +i);
v.emplace_back(b, -i);
}
sort(begin(v), end(v));
build(1, 0, n - 1);
vector<pair<int, int>> b(n);
{
auto can = 0, up = 0;
for(auto p : v) {
if(p.second > 0) {
can++;
b[+p.second - 1].first = up;
} else {
b[-p.second - 1].second = up;
auto x = (double)(can - 1) / can;
for(auto u = leaf[up++]; u > 0; u >>= 1) seg[u] *= x;
can--;
}
}
}
for(auto i = 0; i < n; i++) {
ql = b[i].first;
qr = b[i].second - 1;
qx = 1;
if(ql <= qr) go(1, 0, n - 1);
printf("%.15f %.15f\n", 1 - qx, qx * seg[leaf[b[i].second]]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
F - Yakiniku |
User |
arosusti |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
2121 Byte |
Status |
AC |
Exec Time |
294 ms |
Memory |
5808 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:68:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:72:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
^
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 |
29 ms |
996 KB |
subtask0_sample_02.txt |
AC |
26 ms |
952 KB |
subtask0_sample_03.txt |
AC |
25 ms |
1044 KB |
subtask1_random01.txt |
AC |
25 ms |
948 KB |
subtask1_random02.txt |
AC |
28 ms |
1044 KB |
subtask1_random03.txt |
AC |
26 ms |
1048 KB |
subtask1_random04.txt |
AC |
26 ms |
936 KB |
subtask1_random05.txt |
AC |
26 ms |
1044 KB |
subtask1_random06.txt |
AC |
29 ms |
872 KB |
subtask1_random07.txt |
AC |
27 ms |
1044 KB |
subtask1_random08.txt |
AC |
26 ms |
1048 KB |
subtask1_random09.txt |
AC |
282 ms |
5668 KB |
subtask1_random10.txt |
AC |
286 ms |
5716 KB |
subtask1_random11.txt |
AC |
284 ms |
5664 KB |
subtask1_random12.txt |
AC |
294 ms |
5808 KB |
subtask1_random13.txt |
AC |
285 ms |
5668 KB |
subtask1_special01.txt |
AC |
237 ms |
5668 KB |
subtask1_special02.txt |
AC |
228 ms |
5624 KB |
subtask1_special03.txt |
AC |
241 ms |
5720 KB |
subtask1_special04.txt |
AC |
28 ms |
972 KB |
subtask1_special05.txt |
AC |
27 ms |
952 KB |
subtask1_special06.txt |
AC |
26 ms |
1048 KB |