QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#94475 | #5385. Goblin Garden Guards | DoubleAS | TL | 834ms | 70384kb | C++14 | 4.2kb | 2023-04-06 11:50:58 | 2023-04-06 11:50:59 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
//using namespace chrono;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< int > vi;
typedef vector< ll > V;
typedef map<int, int > mp;
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define F first
#define S second
#define debug cout << -1 << endl;
#define REP(i, a, b) for(int i=a; i<b; i++)
#define f0r(i, n) for (int i = 0; i < n; ++i)
#define f0r1(i, n) for (int i = 1; i <= n; ++i)
#define r0f(i, n) for(int i=n-1; i>=0; i--)
#define r0f1(i, n) for(int i=n; i>=1; i--)
#define fore(a, x) for (auto& a : x)
#define fori(i, a, b) for (int i = (a); i < (b); ++i)
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define nw cout << "\n"
#define issq(x) (((ll)(sqrt((x))))*((ll)(sqrt((x))))==(x))
#define rev(v) reverse(v.begin(),v.end())
#define asche cerr<<"Ekhane asche\n";
#define rev(v) reverse(v.begin(),v.end())
#define srt(v) sort(v.begin(),v.end())
#define grtsrt(v) sort(v.begin(),v.end(),greater<ll>())
#define all(v) v.begin(),v.end()
#define mnv(v) *min_element(v.begin(),v.end())
#define mxv(v) *max_element(v.begin(),v.end())
#define valid(tx,ty) (tx>=0 && tx<r && ty>=0 && ty<n)
#define one(x) __builtin_popcount(x)
#define dag cerr << "-----------------------------------------\n";
// #define pop pop_back
#define setPrec(x) cout << fixed << setprecision(x)
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
int count(int l, int r, ordered_set &st) {
return st.order_of_key(r+1) - st.order_of_key(l);
}
// #define sz(a) (int)a.sz()
//#define fin cin
//#define fout cout
const int INF = 1e9;
const ll MOD = (ll)1e9+7;
const ll INFL = 1e18;
const ll mnINF = -1e18;
const double diff = 10e-6;
const int maxn = 1000002;
const int MX = 100002;
const double PI = acos(-1);
using namespace std;
#define MAX 10000002
const double bruh = .00000001;
// int dx[] = {-1, 0, 1};
// int dy[] = {-1, 0, 1};
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
// int dx[] = {0, 1};
// int dy[] = {-1, 0};
const int N = 1002;
void solve()
{
int g, n;
cin >> g;
// map< int, ordered_set > m;
map< pair< int, int >, int > a;
int mn = INF, mx = 0;
f0r(i, g) {
int x, y;
cin >> x >> y;
// m[x].insert(y);
// m[y].insert(x);
mn = min(mn, x);
mx = max(mx, x);
a[{x, y}]++;
}
cin >> n;
int ans = 0;
f0r(i, n) {
int x, y, r;
cin >> x >> y >> r;
for(int i=max(x-r, mn); i<=min(x+r, mx); i++) {
int dx = abs(x-i);
for(int j=y-r; j<=y+r; j++) {
int dy = abs(y-j);
if(dx*dx+dy*dy<=r*r) {
ans += a[{i, j}];
a[{i,j}] = 0;
}
}
}
}
cout << g-ans << "\n";
}
void setIO(string name = "") { // name is nonempty for USACO file I/O
ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
// alternatively, cin.tie(0)->sync_with_stdio(0);
if (name.size()) {
freopen((name+".in").c_str(), "r", stdin); // see Input & Output
freopen((name+".out").c_str(), "w", stdout);
}
}
int32_t main()
{
//#ifndef ONLINE_JUDGE
// freopen("inputf.in", "r", stdin);
// freopen("outputf.in", "w", stdout);
//#endif
// setIO("gates");
// freopen("ariprog.in","r",stdin);
// freopen("ariprog.out","w",stdout);
FastIO;
// freopen("lightson.in","r",stdin);
// freopen("lightson.out","w",stdout);
int t;
t = 1;
// preCalc();
// memset(dp, -1, szof(dp));
// cin >> t;
// cin.ignore();
for(int i=0; i<t; i++) {
// if(i) nw;
// cout << "Case " << i+1 << ": ";
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
5 0 0 100 0 0 100 100 100 50 50 1 0 0 50
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 8ms
memory: 4528kb
input:
10 13 49 55 85 93 67 78 30 43 69 33 73 70 31 70 3 90 51 18 62 5 23 82 96 78 12 66 97 24 16 12 97 83 55 97 13
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 4ms
memory: 4028kb
input:
10 23 73 22 32 36 98 32 26 36 53 62 76 55 31 72 60 58 41 62 38 5 96 92 55 99 82 63 63 82 2 26 4 73 10 83 22
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 8ms
memory: 4428kb
input:
10 49 59 6 100 76 4 97 6 69 33 74 45 22 17 68 21 69 24 43 68 5 62 10 44 89 51 69 29 71 9 76 45 93 93 22 10
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 834ms
memory: 70260kb
input:
1000 747 966 416 548 315 882 117 681 281 686 455 328 61 407 78 524 163 777 882 940 405 849 588 521 3 33 938 621 790 148 191 962 76 678 803 557 594 797 355 744 769 726 172 969 126 426 294 710 791 501 305 972 855 567 435 574 133 497 762 765 380 183 184 710 366 158 281 709 550 695 443 114 490 951 350 3...
output:
11
result:
ok single line: '11'
Test #6:
score: 0
Accepted
time: 827ms
memory: 69852kb
input:
1000 944 686 158 832 830 715 825 422 684 278 439 357 835 43 451 239 12 891 193 934 439 492 941 391 1 861 514 726 749 279 960 777 397 675 212 988 647 455 850 52 504 508 692 426 668 466 640 255 359 849 329 778 303 542 59 153 44 752 67 785 840 193 959 420 888 636 836 719 260 930 471 89 498 387 371 421 ...
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 817ms
memory: 70384kb
input:
1000 549 340 949 478 60 731 879 508 551 508 249 856 66 165 110 340 184 986 463 589 574 891 717 618 409 705 461 14 460 505 175 276 421 34 697 407 599 925 69 960 809 805 415 937 279 92 991 331 224 243 129 234 300 858 975 906 409 208 88 618 558 371 199 471 76 345 168 967 552 743 412 216 784 416 520 823...
output:
14
result:
ok single line: '14'
Test #8:
score: -100
Time Limit Exceeded
input:
100000 409 6634 9449 147 1470 849 6318 3524 5520 6083 9470 3654 6593 7593 5940 2178 431 6018 9365 9214 7642 1035 5625 8881 9246 9373 3686 591 8987 3816 9407 5447 8205 2547 1514 3786 3771 9010 1965 3802 4856 5457 4023 1006 8187 4363 332 167 2946 837 6965 6280 5853 2781 1524 745 2912 5955 3371 4754 83...