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