oj.uz

답안 #482533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482533 2021-10-25T11:47:21 Z nicolaalexandra Pairs (IOI07_pairs) C++14
45 / 100
 278 ms 16636 KB 
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;

struct point{
    int x,y,z;
} v[DIM];

int aib[DIM];
long long sp[80][160][160];

int n,m,c,d,i,j,x,y,z,k;

inline int cmp (point a, point b){
    return a.x < b.x;
}

inline int cmp2 (point a, point b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void update (int p, int val){
    for (;p<=m;p+=(p&-p))
        aib[p] += val;
}

int query (int p){
    if (p <= 0)
        return 0;

    int sol = 0;
    for (;p;p-=(p&-p))
        sol += aib[p];
    return sol;
}
long long modul (long long n){
    return max (n,-n);
}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>c>>n>>d>>m;

    if (c == 1){
        for (i=1;i<=n;i++)
            cin>>v[i].x;

        sort (v+1,v+n+1,cmp);

        long long ans = 0;
        for (i=1;i<=n;i++){

            int st = 1, dr = i, sol = 0;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (v[i].x - v[mid].x <= d){
                    sol = mid;
                    dr = mid-1;
                } else st = mid+1;
            }

            ans += i - sol;

        }

        cout<<ans;

        return 0;
    }

    if (c == 2){

        for (i=1;i<=n;i++){
            cin>>x>>y;
            v[i].x = x+y-1;
            v[i].y = m-x+y;
        }
        m *= 2;
        sort (v+1,v+n+1,cmp2);

        int poz = 1;
        long long ans = 0;

        for (i=1;i<=n;i++){

            update (v[i].y,1);

            while (v[poz].x + d < v[i].x){
                update (v[poz].y,-1);
                poz++;
            }

            ans += query (min(m,v[i].y + d)) - query (max(0,v[i].y - d - 1));

        }

        cout<<ans - n;

        return 0;
    }


    for (i=1;i<=n;i++){
        cin>>x>>y>>z;
        v[i] = {x+y-1,m-x+y,z};
        sp[z][v[i].x][v[i].y]++;
    }

    for (i=1;i<=m;i++)
        for (j=1;j<=2*m;j++)
            for (k=1;k<=2*m;k++)
                sp[i][j][k] += sp[i][j-1][k] + sp[i][j][k-1] - sp[i][j-1][k-1];

    long long ans = 0;
    for (i=1;i<=n;i++){
        x = v[i].x, y = v[i].y;
        for (z=1;z<=m;z++){
            if (z == 10 || z == 20)
                z = z;
            int val = d - modul (z - v[i].z);
            if (val < 0)
                continue;
            ans += sp[z][x][y] - sp[z][max(0,x-val-1)][y] - sp[z][x][max(0,y-val-1)] + sp[z][max(0,x-val-1)][max(0,y-val-1)];
        }
    }

    cout<<ans - n;


    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 1724 KB Output is correct
2 Correct 30 ms 1816 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 2260 KB Output is correct
2 Correct 49 ms 2252 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 2316 KB Output is correct
2 Correct 47 ms 2312 KB Output is correct
3 Correct 60 ms 2220 KB Output is correct

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 1944 KB Output is correct
2 Correct 44 ms 1988 KB Output is correct

Subtask #8
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 2236 KB Output is correct
2 Correct 62 ms 2276 KB Output is correct
3 Correct 55 ms 2188 KB Output is correct
4 Correct 52 ms 2112 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 77 ms 3040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 14744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 2252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 11716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 278 ms 16636 KB Output isn't correct
2 Halted 0 ms 0 KB -