Submission #60442

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define repc(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define var(type, ...) \
type __VA_ARGS__; \
read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
return vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
return vector<decltype(makeV<T>(initValue, args...))>(
sz, makeV<T>(initValue, args...));
}
template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
for (auto &e : vec) is >> e;
return is;
}
inline void read() {}
template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
cin >> head;
read(tail...);
}
inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
cout << head;
if (sizeof...(tail)) cout << ' ';
print(forward<Tail>(tail)...);
}
template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
static constexpr const char *delim[] = {" ", ""};
for (const auto &e : vec) os << e << delim[&e == &vec.back()];
return os;
}
template <class Container>
struct Rev {
Container &x_;
inline Rev(Container &x) : x_(x) {}
inline auto begin() { return rbegin(x_); }
inline auto end() { return rend(x_); }
};
// }}} End Header
template <class T>
struct FenwickTree { // {{{
vector<T> dat;
const size_t SIZE_POW2;
explicit FenwickTree(int size)
: dat(size + 5, 0), SIZE_POW2(1 << (__lg(size + 5) + 1)) {}
inline void add(int i, const T &v) {
for (++i; i < dat.size(); i += i & -i) dat[i] += v;
}
inline T sum(int i) const {
T s = 0;
for (++i; i > 0; i -= i & -i) s += dat[i];
return s;
;
}
inline T sum(int s, int t) const {
if (s > t) swap(s, t);
return sum(t) - sum(s - 1);
}
inline int lower_bound(T v) const {
if (v <= 0) return 0;
int i = 0;
for (int w = SIZE_POW2; w > 0; w >>= 1) {
if (i + w < dat.size() && dat[i + w] < v) {
v -= dat[i + w];
i += w;
}
}
return i;
}
}; // }}}
inline int norm(int y, int x) { return y * y + x * x; }
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(ios_base::fixed);
cout.precision(6);
var(int, T);
vector<tuple<int, int, int>> queries(T); // vector of (K, L, queryID)
rep(i, 0, T) {
var(int, L, K);
queries[i] = tie(L, K, i);
}
sort(all(queries));
vector<vector<int>> norms(1001);
repc(y, 0, 1000) repc(x, 0, 1000) {
norms[max(y, x)].push_back(norm(y, x));
}
vector<int> ans(T);
FenwickTree<int> ft(norm(1001, 1001));
int curL = 0;
for (const auto [L, K, id] : queries) {
while (curL <= L) {
for (const int d : norms[curL]) ft.add(d, 1);
++curL;
}
ans[id] = ft.lower_bound(K);
}
rep(i, 0, T) print(sqrt(ans[i]));
return 0;
}

ステータス

項目 データ
問題 1353 - Function of Euclidean Distance
ユーザー名 syoribu
投稿日時 2020-07-04 11:02:03
言語 C++17
状態 Accepted
得点 400
ソースコード長 3915 Byte
最大実行時間 140 ms
最大メモリ使用量 25912 KB

セット

セット 得点 Cases
1 task01 60 / 60 in01*, sample01.txt
2 task02 340 / 340 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01_01.txt AC 37 ms 13784 KB
1
2
in01_02.txt AC 56 ms 13732 KB
1
2
in01_03.txt AC 34 ms 13812 KB
1
2
in01_04.txt AC 47 ms 13764 KB
1
2
in01_05.txt AC 53 ms 13712 KB
1
2
in01_06.txt AC 33 ms 13656 KB
1
2
in01_07.txt AC 30 ms 13604 KB
1
2
in01_08.txt AC 32 ms 13688 KB
1
2
in01_09.txt AC 56 ms 13636 KB
1
2
in01_10.txt AC 52 ms 13720 KB
1
2
in02_01.txt AC 124 ms 16480 KB
2
in02_02.txt AC 123 ms 17668 KB
2
in02_03.txt AC 138 ms 18856 KB
2
in02_04.txt AC 88 ms 19536 KB
2
in02_05.txt AC 61 ms 20468 KB
2
in02_06.txt AC 140 ms 21656 KB
2
in02_07.txt AC 137 ms 22716 KB
2
in02_08.txt AC 127 ms 23780 KB
2
in02_09.txt AC 134 ms 24848 KB
2
in02_10.txt AC 140 ms 25912 KB
2
sample01.txt AC 32 ms 24284 KB
1
2
sample02.txt AC 57 ms 24232 KB
2