oj.uz

Submission #262618

# Submission time Handle Problem Language Result Execution time Memory
262618 2020-08-13T05:31:53 Z 문홍윤(#5091) Pairs (IOI07_pairs) C++17
100 / 100
 397 ms 51468 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int n, d, m;

void solve_1d(){
    vector<int> out, qu;
    for(int i=1; i<=n; i++){
        int p;
        scanf("%d", &p);
        out.eb(min(p+d+1, m+1));
        qu.eb(p);
    }
    svec(qu); svec(out);
    LL num=0, ans=0;
    int pv=0;
    for(auto i:qu){
        for(; pv<out.size(); pv++){
            if(out[pv]>i)break;
            num--;
        }
        ans+=num;
        num++;
    }
    printf("%lld", ans);
}

struct FENWICK{
    LL tree[150010];
    LL sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=150000){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
}fen;

void solve_2d(){
    vector<pii> out, qu;
    m*=2;
    for(int i=1; i<=n; i++){
        int p1, p2;
        scanf("%d %d", &p1, &p2);
        out.eb(min(p1+p2+d+1, m+1), p1-p2+m/2);
        qu.eb(p1+p2, p1-p2+m/2);
    }
    svec(qu); svec(out);
    LL ans=0;
    int pv=0;
    for(auto i:qu){
        for(; pv<out.size(); pv++){
            if(out[pv].F>i.F)break;
            fen.update(out[pv].S, -1);
        }
        ans+=fen.sum(min(i.S+d, m))-fen.sum(max(i.S-d-1, 0));
        fen.update(i.S, 1);
    }
    printf("%lld", ans);
}

struct FENWICK_3D{
    LL tree[250][250][250];
    LL sum(int i, int j, int k){
        LL ans=0;
        while(i){
            int tj=j, tk=k;
            while(j){
                int tk2=k;
                while(k){
                    ans+=tree[i][j][k];
                    k-=(k&-k);
                }
                k=tk2;
                j-=(j&-j);
            }
            j=tj, k=tk;
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, int j, int k, LL num){
        while(i<=225){
            int tj=j, tk=k;
            while(j<=225){
                int tk2=k;
                while(k<=225){
                    tree[i][j][k]+=num;
                    k+=(k&-k);
                }
                k=tk2;
                j+=(j&-j);
            }
            j=tj, k=tk;
            i+=(i&-i);
        }
    }
}fen3d;

void solve_3d(){
    vector<pair<pii, pii> > out, qu;
    m*=3;
    for(int i=1; i<=n; i++){
        int p1, p2, p3;
        scanf("%d %d %d", &p1, &p2, &p3);
        out.eb(mp(min(p1+p2+p3+d+1, m+1), p1+p2-p3+m/3), mp(p1-p2+p3+m/3, p1-p2-p3+m/3*2));
        qu.eb(mp(p1+p2+p3, p1+p2-p3+m/3), mp(p1-p2+p3+m/3, p1-p2-p3+m/3*2));
    }
    svec(qu); svec(out);
    LL ans=0;
    int pv=0;
    for(auto i:qu){
        for(; pv<out.size(); pv++){
            if(out[pv].F.F>i.F.F)break;
            fen3d.update(out[pv].F.S, out[pv].S.F, out[pv].S.S, -1);
        }
        ans+=fen3d.sum(min(i.F.S+d, m), min(i.S.F+d, m), min(i.S.S+d, m));
        ans-=fen3d.sum(max(i.F.S-d-1, 0), min(i.S.F+d, m), min(i.S.S+d, m));
        ans-=fen3d.sum(min(i.F.S+d, m), max(i.S.F-d-1, 0), min(i.S.S+d, m));
        ans-=fen3d.sum(min(i.F.S+d, m), min(i.S.F+d, m), max(i.S.S-d-1, 0));
        ans+=fen3d.sum(max(i.F.S-d-1, 0), max(i.S.F-d-1, 0), min(i.S.S+d, m));
        ans+=fen3d.sum(max(i.F.S-d-1, 0), min(i.S.F+d, m), max(i.S.S-d-1, 0));
        ans+=fen3d.sum(min(i.F.S+d, m), max(i.S.F-d-1, 0), max(i.S.S-d-1, 0));
        ans-=fen3d.sum(max(i.F.S-d-1, 0), max(i.S.F-d-1, 0), max(i.S.S-d-1, 0));
        fen3d.update(i.F.S, i.S.F, i.S.S, 1);
    }
    printf("%lld", ans);
}

int main(){
    int dim;
    scanf("%d", &dim);
    scanf("%d %d %d", &n, &d, &m);
    if(dim==1)solve_1d();
    if(dim==2)solve_2d();
    if(dim==3)solve_3d();
}

/*
3 8 10 20
10 10 10
10 10 20
10 20 10
10 20 20
20 10 10
20 10 20
20 20 10
20 20 20
*/

Compilation message

pairs.cpp: In function 'void solve_1d()':
pairs.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(; pv<out.size(); pv++){
      |               ~~^~~~~~~~~~~
pairs.cpp: In function 'void solve_2d()':
pairs.cpp:66:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(; pv<out.size(); pv++){
      |               ~~^~~~~~~~~~~
pairs.cpp: In function 'void solve_3d()':
pairs.cpp:127:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(; pv<out.size(); pv++){
      |               ~~^~~~~~~~~~~
pairs.cpp: In function 'void solve_1d()':
pairs.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~
pairs.cpp: In function 'void solve_2d()':
pairs.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |         scanf("%d %d", &p1, &p2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'void solve_3d()':
pairs.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |         scanf("%d %d %d", &p1, &p2, &p3);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp: In function 'int main()':
pairs.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |     scanf("%d", &dim);
      |     ~~~~~^~~~~~~~~~~~
pairs.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  147 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1404 KB Output is correct
2 Correct 24 ms 1404 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1536 KB Output is correct
2 Correct 30 ms 1532 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1524 KB Output is correct
2 Correct 40 ms 1532 KB Output is correct
3 Correct 34 ms 1532 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1408 KB Output is correct
2 Correct 2 ms 1408 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2292 KB Output is correct
2 Correct 48 ms 2784 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2488 KB Output is correct
2 Correct 56 ms 2916 KB Output is correct
3 Correct 55 ms 2916 KB Output is correct
4 Correct 61 ms 2916 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3416 KB Output is correct
2 Correct 59 ms 4324 KB Output is correct
3 Correct 62 ms 4324 KB Output is correct
4 Correct 56 ms 4324 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18304 KB Output is correct
2 Correct 10 ms 18304 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 5564 KB Output is correct
2 Correct 127 ms 5968 KB Output is correct
3 Correct 98 ms 5968 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 35096 KB Output is correct
2 Correct 262 ms 35540 KB Output is correct
3 Correct 123 ms 35540 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 50772 KB Output is correct
2 Correct 316 ms 51468 KB Output is correct
3 Correct 148 ms 51412 KB Output is correct