oj.uz

Submission #914707

# Submission time Handle Problem Language Result Execution time Memory
914707 2024-01-22T14:58:46 Z bachhoangxuan Dragon 2 (JOI17_dragon2) C++17
100 / 100
 2086 ms 3984 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x),erase(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/

#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define mpp make_pair
#define fi first
#define se second
const int inf=1e18;
const int mod=998244353;
const int maxn=30005;
const int bl=650;
const int maxs=655;
const int maxm=200005;
const int maxq=1000005;
const int maxl=25;
const int maxa=1000000;
const int root=3;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
const int iroot=power(3,mod-2);
const int base=131;

int n,m,q;
vector<pii> p[maxn];

bool cross(pii x,pii y,pii z){
    return (x.fi-y.fi)*(z.se-y.se)-(z.fi-y.fi)*(x.se-y.se)<=0;
}

void solve(){
    cin >> n >> m;
    pii A,B;
    for(int i=1;i<=n;i++){
        int x;cin >> A.fi >> A.se >> x;
        p[x].push_back(A);
    }
    cin >> A.fi >> A.se >> B.fi >> B.se;
    cin >> q;
    for(int i=1;i<=q;i++){
        int x,y;cin >> x >> y;
        int M=0;
        for(auto i:p[x]) for(auto j:p[y]){
            if(cross(i,A,B)) M+=(cross(i,A,j) && cross(j,B,i));
            else M+=(cross(j,A,i) && cross(i,B,j));
        }
        cout << M << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1116 KB Output is correct
2 Correct 15 ms 1368 KB Output is correct
3 Correct 21 ms 1372 KB Output is correct
4 Correct 26 ms 2132 KB Output is correct
5 Correct 21 ms 2396 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 5 ms 1116 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 2456 KB Output is correct
2 Correct 1598 ms 2512 KB Output is correct
3 Correct 40 ms 2652 KB Output is correct
4 Correct 10 ms 2652 KB Output is correct
5 Correct 10 ms 2552 KB Output is correct
6 Correct 859 ms 2528 KB Output is correct
7 Correct 810 ms 2536 KB Output is correct
8 Correct 423 ms 2520 KB Output is correct
9 Correct 412 ms 2272 KB Output is correct
10 Correct 449 ms 2512 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1116 KB Output is correct
2 Correct 15 ms 1368 KB Output is correct
3 Correct 21 ms 1372 KB Output is correct
4 Correct 26 ms 2132 KB Output is correct
5 Correct 21 ms 2396 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 5 ms 1116 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 850 ms 2456 KB Output is correct
12 Correct 1598 ms 2512 KB Output is correct
13 Correct 40 ms 2652 KB Output is correct
14 Correct 10 ms 2652 KB Output is correct
15 Correct 10 ms 2552 KB Output is correct
16 Correct 859 ms 2528 KB Output is correct
17 Correct 810 ms 2536 KB Output is correct
18 Correct 423 ms 2520 KB Output is correct
19 Correct 412 ms 2272 KB Output is correct
20 Correct 449 ms 2512 KB Output is correct
21 Correct 863 ms 2536 KB Output is correct
22 Correct 1622 ms 2516 KB Output is correct
23 Correct 1659 ms 2848 KB Output is correct
24 Correct 470 ms 3984 KB Output is correct
25 Correct 35 ms 3668 KB Output is correct
26 Correct 42 ms 3888 KB Output is correct
27 Correct 12 ms 3032 KB Output is correct
28 Correct 18 ms 2876 KB Output is correct
29 Correct 2086 ms 3732 KB Output is correct
30 Correct 52 ms 3532 KB Output is correct
31 Correct 28 ms 3800 KB Output is correct
32 Correct 58 ms 3860 KB Output is correct
33 Correct 430 ms 3868 KB Output is correct
34 Correct 32 ms 3876 KB Output is correct
35 Correct 29 ms 3668 KB Output is correct
36 Correct 30 ms 3788 KB Output is correct
37 Correct 41 ms 3860 KB Output is correct
38 Correct 718 ms 3800 KB Output is correct
39 Correct 544 ms 3696 KB Output is correct
40 Correct 455 ms 3796 KB Output is correct
41 Correct 1865 ms 3568 KB Output is correct
42 Correct 1299 ms 3504 KB Output is correct
43 Correct 991 ms 3576 KB Output is correct
44 Correct 1284 ms 2888 KB Output is correct
45 Correct 631 ms 2900 KB Output is correct
46 Correct 373 ms 2652 KB Output is correct
47 Correct 913 ms 2768 KB Output is correct
48 Correct 572 ms 2632 KB Output is correct
49 Correct 328 ms 2804 KB Output is correct