QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94475#5385. Goblin Garden GuardsDoubleASTL 834ms70384kbC++144.2kb2023-04-06 11:50:582023-04-06 11:50:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-06 11:50:59]
  • 评测
  • 测评结果:TL
  • 用时:834ms
  • 内存:70384kb
  • [2023-04-06 11:50:58]
  • 提交

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

output:


result: