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
|