Submission #60685


ソースコード

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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using VS = vector<string>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define eFOR(i,a,n) for(int i=(a);i<=(n);++i)
#define rFOR(i,a,n) for(int i=(n)-1;i>=(a);--i)
#define erFOR(i,a,n) for(int i=(n);i>=(a);--i)
#define each(i, a) for(auto &i : a)
#define SORT(a) sort(a.begin(),a.end())
#define rSORT(a) sort(a.rbegin(),a.rend())
#define fSORT(a,f) sort(a.begin(),a.end(),f)
#define all(a) a.begin(),a.end()
#define out(y,x) ((y)<0||h<=(y)||(x)<0||w<=(x))
#define tp(a,i) get<i>(a)
#define line cout << "-----------------------------\n"
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
template<class T>inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline istream& operator>>(istream& is, deque<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts>inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T>inline void print(const vector<vector<T>>& v) { for (auto& a : v)print(a); }
inline string reversed(const string& s) { string t = s; reverse(all(t)); return t; }
template<class T> class segtree {
using F1 = function<T(T, T)>;
using F2 = function<void(T&, T)>;
using F3 = function<bool(T, T)>;
T unit;
F1 f1;
F2 f2;
F3 f3; bool s3 = false;
int n, real_n;
vector<T> dat;
vector<pair<int, int>> range;
public:
segtree() {}
segtree(const int& _n, const F1& _f1, const F2& _f2, const T _unit)
: real_n(_n), f1(_f1), f2(_f2), unit(_unit) {
init1();
}
segtree(const int& _n, const F1& _f1, const F2& _f2, const F3& _f3, const T _unit)
: real_n(_n), f1(_f1), f2(_f2), f3(_f3), unit(_unit), s3(true) {
init1(), init2();
}
segtree(const vector<T>& _dat, const F1& _f1, const F2& _f2, const T _unit)
: real_n(_dat.size()), f1(_f1), f2(_f2), unit(_unit) {
init1();
FOR(i, 0, real_n)dat[i + n] = _dat[i];
init2(true);
}
segtree(const vector<T>& _dat, const F1& _f1, const F2& _f2, const F3& _f3, const T _unit)
: real_n(_dat.size()), f1(_f1), f2(_f2), f3(_f3), unit(_unit), s3(true) {
init1();
FOR(i, 0, real_n)dat[i + n] = _dat[i];
init2(true);
}
inline void init1() {
n = 1;
while (n < real_n)n <<= 1;
dat.assign(n << 1, unit);
if (s3)range.assign(n << 1, { 0,0 });
}
inline void init2(bool with_array = false) {
if (s3)FOR(i, 0, n)range[n + i] = make_pair(i, i + 1);
rFOR(i, 1, n) {
if (with_array)dat[i] = f1(dat[i << 1], dat[i << 1 | 1]);
if (s3)range[i] = make_pair(range[i << 1].first, range[i << 1 | 1].second);
}
}
inline void update(int i, T a) {
i += n;
f2(dat[i], a);
while (1 < i) {
i >>= 1;
dat[i] = f1(dat[i << 1], dat[i << 1 | 1]);
}
}
inline T value(int l, int r) {
T ret = unit;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1)ret = f1(ret, dat[l++]);
if (r & 1)ret = f1(ret, dat[--r]);
}
return ret;
}
inline int binary_search(T a) {
assert(s3);
if (!f3(dat[1], a))return real_n;
int idx = 2;
T cur = unit;
for (; idx < n << 1; idx <<= 1) {
if (!f3(f1(cur, dat[idx]), a)) {
cur = f1(cur, dat[idx++]);
}
}
return min((idx >> 1) - n, real_n);
}
inline int binary_search(int l, int r, T a) {
assert(s3);
T cur = unit;
int ret = l;
for (int idx = n + l; idx < n << 1 && ret < r;) {
if (range[idx].second <= r && !f3(f1(cur, dat[idx]), a)) {
cur = f1(cur, dat[idx]);
ret = range[idx++].second;
if (!(idx & 1))idx >>= 1;
}
else idx <<= 1;
}
return ret;
}
inline T operator[](int i) { return dat[i + n]; }
};
using d = double;
int main() {
init();
int q; cin >> q;
vector<tuple<int, int, int>> t;
t.reserve(q);
FOR(i, 0, q) {
int l, k; cin >> l >> k;
t.emplace_back(l, k, i);
}
SORT(t);
map<d, int> ma;
eFOR(y, 0, 1000)eFOR(x, 0, 1000)ma[sqrt(y * y + x * x)];
vector<d> mi(ma.size());
{
int c = 0;
for (auto itr = ma.begin(); itr != ma.end(); ++itr, ++c) {
itr->second = c;
mi[c] = itr->first;
}
}
segtree<int> seg(VI(ma.size()),
[](int x, int y) {return x + y; },
[](int& x, int y) {x += y; },
[](int x, int y) {return y <= x; }, 0);
vector<d> ans(q);
for (int i = 0, idx = 0; i <= 1000; ++i) {
FOR(y, 0, i)seg.update(ma[sqrt(y * y + i * i)], 2);
seg.update(ma[sqrt(i * i * 2)], 1);
for (; idx < q && tp(t[idx], 0) == i; ++idx) {
ans[tp(t[idx], 2)] = mi[seg.binary_search(tp(t[idx], 1))];
}
}
each(i, ans)print(i);
return 0;
}

ステータス

項目 データ
問題 1353 - Function of Euclidean Distance
ユーザー名 ir_1st_vil
投稿日時 2020-07-12 22:04:31
言語 C++17
状態 Accepted
得点 400
ソースコード長 6170 Byte
最大実行時間 524 ms
最大メモリ使用量 55176 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01_01.txt AC 375 ms 35164 KB
1
2
in01_02.txt AC 365 ms 34996 KB
1
2
in01_03.txt AC 365 ms 34960 KB
1
2
in01_04.txt AC 373 ms 35052 KB
1
2
in01_05.txt AC 362 ms 35012 KB
1
2
in01_06.txt AC 383 ms 35104 KB
1
2
in01_07.txt AC 376 ms 35068 KB
1
2
in01_08.txt AC 377 ms 35164 KB
1
2
in01_09.txt AC 387 ms 35004 KB
1
2
in01_10.txt AC 362 ms 35220 KB
1
2
in02_01.txt AC 485 ms 37976 KB
2
in02_02.txt AC 502 ms 40072 KB
2
in02_03.txt AC 515 ms 41912 KB
2
in02_04.txt AC 417 ms 43756 KB
2
in02_05.txt AC 424 ms 45596 KB
2
in02_06.txt AC 502 ms 47560 KB
2
in02_07.txt AC 524 ms 49400 KB
2
in02_08.txt AC 497 ms 51244 KB
2
in02_09.txt AC 497 ms 53336 KB
2
in02_10.txt AC 500 ms 55176 KB
2
sample01.txt AC 372 ms 54476 KB
1
2
sample02.txt AC 366 ms 54436 KB
2