oj.uz

답안 #292155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292155 2020-09-06T13:00:24 Z Kastanda Pairs (IOI07_pairs) C++11
70 / 100
 4000 ms 189456 KB 
// M
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
template < typename T >
using ordered_set = tree < T , null_type , less < T > , rb_tree_tag, tree_order_statistics_node_update >;
const int N = 100005, MX2D = 75005, MX3D = 77;
int n, m, d, Mxd, ts, B[N];
vector < int > A[N];
ordered_set < ll > S2D[MX2D], S3D[MX3D][MX3D];
inline void Add2D(int a, int val)
{
        ll vl = val * (ll)(1e6) + ts; ts ++;
        for (a ++; a < MX2D; a += a & - a)
                S2D[a].insert(vl);
}
inline int Count2D(int a, int val)
{
        int rt = 0;
        ll vl = val * (ll)(1e6) - 1;
        for (; a; a -= a & - a)
                rt += (int)S2D[a].size() - S2D[a].order_of_key(vl);
        return rt;
}
inline void Add3D(int a, int b, int val)
{
        ll vl = val * (ll)(1e6) + ts; ts ++;
        for (a ++; a < MX3D; a += a & - a)
                for (int d = b + 1; d < MX3D; d += d & - d)
                        S3D[a][d].insert(vl);
}
inline int Count3D(int a, int b, int val)
{
        int rt = 0;
        ll vl = val * (ll)(1e6) - 1;
        for (; a; a -= a & - a)
                for (int d = b; d; d -= d & - d)
                        rt += (int)S3D[a][d].size() - S3D[a][d].order_of_key(vl);
        return rt;
}
int main()
{
        scanf("%d%d%d%d", &d, &n, &Mxd, &m);
        if (d == 1)
        {
                ll tot = 0;
                for (int i = 1; i <= n; i ++)
                        scanf("%d", &B[i]);
                sort(B + 1, B + n + 1);
                for (int i = 1; i <= n; i ++)
                        tot += (int)(upper_bound(B + 1, B + n + 1, B[i] + Mxd) - B) - i - 1;
                return !printf("%lld\n", tot);
        }
        for (int i = 1; i <= n; i ++)
        {
                A[i] = vector < int > (d, 0);
                for (int j = 0; j < d; j ++)
                        scanf("%d", &A[i][j]);
        }
        sort(A + 1, A + n + 1);
        if (d == 2)
        {
                ll tot = 0;
                for (int wy = 0; wy < 2; wy ++)
                {
                        for (int i = 1; i <= n; i ++)
                        {
                                int vl = A[i][0] + A[i][1];
                                tot += Count2D(A[i][1] + wy, vl - Mxd);
                                Add2D(A[i][1], vl);
                        }
                        for (int i = 1; i <= n; i ++)
                                A[i][1] = MX2D - A[i][1] - 1;
                        for (int i = 0; i < MX2D; i ++)
                                S2D[i].clear();
                }
                return !printf("%lld\n", tot);
        }
        ll tot = 0;
        for (int wy = 0; wy < 2; wy ++)
        {
                for (int wz = 0; wz < 2; wz ++)
                {
                        for (int i = 1; i <= n; i ++)
                        {
                                int vl = A[i][0] + A[i][1] + A[i][2];
                                tot += Count3D(A[i][1] + wy, A[i][2] + wz, vl - Mxd);
                                Add3D(A[i][1], A[i][2], vl);
                        }
                        for (int i = 1; i <= n; i ++)
                                A[i][2] = MX3D - A[i][2] - 1;
                        for (int i = 0; i < MX3D; i ++)
                                for (int j = 0; j < MX3D; j ++)
                                        S3D[i][j].clear();
                }
                for (int i = 1; i <= n; i ++)
                        A[i][1] = MX3D - A[i][1] - 1;
        }
        return !printf("%lld\n", tot);
}

Compilation message

pairs.cpp: In function 'int main()':
pairs.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         scanf("%d%d%d%d", &d, &n, &Mxd, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:51:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |                         scanf("%d", &B[i]);
      |                         ~~~~~^~~~~~~~~~~~~
pairs.cpp:61:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |                         scanf("%d", &A[i][j]);
      |                         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10240 KB Output is correct
2 Correct 10 ms 10240 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10240 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 10624 KB Output is correct
2 Correct 29 ms 10624 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 10624 KB Output is correct
2 Correct 36 ms 10624 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 10616 KB Output is correct
2 Correct 39 ms 10752 KB Output is correct
3 Correct 36 ms 10624 KB Output is correct

Subtask #6
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 10880 KB Output is correct
2 Correct 15 ms 10880 KB Output is correct

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1286 ms 99932 KB Output is correct
2 Correct 1213 ms 100068 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2433 ms 89024 KB Output is correct
2 Correct 2406 ms 89132 KB Output is correct
3 Correct 1900 ms 90612 KB Output is correct
4 Correct 1988 ms 89532 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2708 ms 69880 KB Output is correct
2 Correct 2569 ms 69696 KB Output is correct
3 Correct 1275 ms 71928 KB Output is correct
4 Correct 1825 ms 77560 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 11136 KB Output is correct
2 Correct 21 ms 11136 KB Output is correct

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4045 ms 189456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4051 ms 117292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4059 ms 99004 KB Time limit exceeded
2 Halted 0 ms 0 KB -